Search Blogs

Showing results for "Suffix"

Found 3 results

Left and Right Sum Differences

LeetCode 2574: Left and Right Sum Differences (Java)The Left and Right Sum Difference problem is a classic array manipulation challenge. It tests your ability to efficiently calculate prefix and suffix values—a skill essential for more advanced algorithms like "Product of Array Except Self."🔗 ResourcesProblem Link: LeetCode 2574 - Left and Right Sum Differences📝 Problem StatementYou are given a 0-indexed integer array nums. You need to return an array answer of the same length where:answer[i] = |leftSum[i] - rightSum[i]|leftSum[i] is the sum of elements to the left of index i.rightSum[i] is the sum of elements to the right of index i.💡 Approach 1: The Three-Array Method (Beginner Friendly)This approach is highly intuitive. We pre-calculate all left sums and all right sums in separate arrays before computing the final difference.The LogicPrefix Array: Fill pref[] by adding the previous element to the cumulative sum.Suffix Array: Fill suff[] by iterating backward from the end of the array.Result: Loop one last time to calculate Math.abs(pref[i] - suff[i]).Java Implementationpublic int[] leftRightDifference(int[] nums) {int n = nums.length;int[] pref = new int[n];int[] suff = new int[n];int[] ans = new int[n];// Calculate Left Sums (Prefix)for (int i = 1; i < n; i++) {pref[i] = pref[i - 1] + nums[i - 1];}// Calculate Right Sums (Suffix)for (int i = n - 2; i >= 0; i--) {suff[i] = suff[i + 1] + nums[i + 1];}// Combine resultsfor (int i = 0; i < n; i++) {ans[i] = Math.abs(pref[i] - suff[i]);}return ans;}Time Complexity: O(n)Space Complexity: O(n) (Uses extra space for pref and suff arrays).🚀 Approach 2: The Running Sum Method (Space Optimized)In technical interviews, you should aim for O(1) extra space. Instead of storing every suffix sum, we calculate the Total Sum first and derive the right sum using logic.The LogicWe use the mathematical property:Right Sum = Total Sum - Left Sum - Current ElementBy maintaining a single variable leftSum that updates as we iterate, we can calculate the result using only the output array.Java Implementationpublic int[] leftRightDifference(int[] nums) {int n = nums.length;int[] ans = new int[n];int totalSum = 0;int leftSum = 0;// 1. Get the total sum of all elementsfor (int num : nums) {totalSum += num;}// 2. Calculate rightSum and difference on the flyfor (int i = 0; i < n; i++) {int rightSum = totalSum - leftSum - nums[i];ans[i] = Math.abs(leftSum - rightSum);// Update leftSum for the next indexleftSum += nums[i];}return ans;}Time Complexity: O(n)Space Complexity: O(1) (Excluding the output array).📊 Summary ComparisonFeatureApproach 1Approach 2Space ComplexityO(n) (Higher)O(1) (Optimal)Logic TypeStorage-basedMathematicalUse CaseBeginnersInterviewsKey TakeawayWhile Approach 1 is easier to visualize, Approach 2 is more professional. It shows you can handle data efficiently without unnecessary memory allocation, which is critical when dealing with large-scale systems.

LeetCodePrefixSuffix

Equilibrium Point

GeeksforGeeks ProblemLink of the Problem to try -: LinkGiven an array of integers arr[], the task is to find the first equilibrium point in the array.The equilibrium point in an array is an index (0-based indexing) such that the sum of all elements before that index is the same as the sum of elements after it. Return -1 if no such point exists.Examples:Input: arr[] = [1, 2, 0, 3]Output: 2Explanation: The sum of left of index 2 is 1 + 2 = 3 and sum on right of index 2 is 3.Input: arr[] = [1, 1, 1, 1]Output: -1Explanation: There is no equilibrium index in the array.Input: arr[] = [-7, 1, 5, 2, -4, 3, 0]Output: 3Explanation: The sum of left of index 3 is -7 + 1 + 5 = -1 and sum on right of index 3 is -4 + 3 + 0 = -1.Constraints:3 <= arr.size() <= 105-104 <= arr[i] <= 104Solution:Solving the Equilibrium Index ProblemThe core logic of this problem is finding the Prefix Sum and Suffix Sum. The goal is to identify the specific index where the sum of elements on the left equals the sum of elements on the right.For beginners, this problem can feel difficult because it isn't immediately obvious how to "balance" the two sides of an array. Understanding these two concepts makes the solution simple:Prefix Sum: The cumulative sum of elements from left to right. We store the total sum at each index as we move forward.Suffix Sum: The cumulative sum of elements from right to left. We store the total sum at each index as we move backward.By comparing these two sums, you can easily find the Equilibrium Point where the two halves of the array are equal.Code:class Solution {// Function to find equilibrium point in the array.public static int findEquilibrium(int arr[]) {// code hereint prefix[] = new int[arr.length];int suffix[] = new int[arr.length];int presum=0;for(int i=0;i<arr.length;i++){presum+=arr[i];prefix[i] = presum;}int suffsum=0;for(int i=arr.length-1;i>=0;i--){suffsum+=arr[i];suffix[i] = suffsum;}for(int i=0;i<suffix.length;i++){if(suffix[i] == prefix[i]){return i;}}return -1;}}

GeeksforGeeksPrefix SumEasy

Count the Number of Good Subarrays – Apple OA DSA Problem & Java Solution

IntroductionThis is an interesting question asked in the Apple OA because the condition is slightly different from the usual subarray problems.Instead of asking whether a subarray itself satisfies some property, the task is to remove a subarray and check whether the elements left behind are strictly increasing.The challenge is to count every possible contiguous subarray whose removal leaves a strictly increasing sequence.With n as large as 10⁵, a direct brute-force solution becomes extremely expensive, making this a good problem for thinking about how the structure of the array can be exploited.Problem StatementGiven an integer array arr of size n, find the number of good subarrays.A subarray arr[l...r] is called good if, after removing all elements from index l through r, the remaining elements form a strictly increasing array.In other words, after removing:arr[l], arr[l+1], ..., arr[r]the elements before l and after r are joined together.The resulting array must satisfy:remaining[i] < remaining[i + 1]for every pair of adjacent elements.Constraints1 ≤ n ≤ 10⁵-10⁹ ≤ arr[i] ≤ 10⁹ExampleConsider:arr = [1, 2, 3, 4, 0, 5]There are 10 good subarrays.Some valid removals are:[0][0, 5][4, 0][4, 0, 5][3, 4, 0][3, 4, 0, 5][2, 3, 4, 0][2, 3, 4, 0, 5][1, 2, 3, 4, 0][1, 2, 3, 4]For example, removing:[3, 4, 0]from:[1, 2, 3, 4, 0, 5]leaves:[1, 2, 5]which is strictly increasing.Therefore, [3,4,0] is a good subarray.Similarly, removing:[0,5]leaves:[1,2,3,4]which is also strictly increasing.Hence:Answer = 10Key ObservationThe array:[1, 2, 3, 4, 0, 5]is already strictly increasing except around:4 → 0Removing a suitable contiguous section containing this problematic portion can reconnect two increasing parts.For example:[1, 2, 3, 4] [0, 5]Removing [0] gives:[1, 2, 3, 4, 5]Removing [4,0] gives:[1, 2, 3, 5]Removing [3,4,0] gives:[1, 2, 5]The important condition is therefore not just whether the removed part is valid. The remaining left and right portions must also connect correctly.Brute-Force Backtracking ApproachA straightforward way to explore the problem is to generate possible selections of indices using recursion.The recursive function maintains:currwhich contains the indices currently selected for removal.For every index, there are two choices:Include the index in the selected set.Do not include the index.Once a selection is created, the ch2() function removes those selected positions and checks whether the remaining array is strictly increasing.A HashSet is also used to avoid counting the same index selection more than once.Checking a CandidateThe ch2() function performs the validation.It first creates an array containing the elements that were not selected for removal.For example:Original:[1, 2, 3, 4, 0, 5]Selected indices:[2, 3, 4]Remaining:[1, 2, 5]Then the remaining array is scanned.If any adjacent pair violates:arr[i] < arr[i + 1]the candidate is rejected.Otherwise, it is considered good.Java SolutionThe following is the provided recursive implementation, with comments added to make the logic easier to follow.public class question {// Stores already counted selections.static int an = 0;static HashSet<List<Integer>> msl = new HashSet<>();// Checks whether removing the selected indices// leaves a strictly increasing array.public static boolean ch2(List<Integer> lis, int[] arr) {// No selected elements means nothing is removed.if (lis.size() == 0) {return false;}// If the entire array is removed,// this implementation does not count it.int[] dum = new int[arr.length - lis.size()];if (dum.length == 0) {return false;}// Store the selected indices.HashSet<Integer> ms = new HashSet<>();for (int a : lis) {ms.add(a);}int c = 0;// Construct the remaining array.for (int i = 0; i < arr.length; i++) {// Keep only indices that were not selected.if (!ms.contains(i)) {dum[c] = arr[i];c++;}}// Check whether the remaining array// is strictly increasing.for (int i = 0; i < dum.length - 1; i++) {if (dum[i] > dum[i + 1]) {return false;}}return true;}public static void main(String[] args) {int[] arr = {1, 2, 3, 4, 0, 5};List<Integer> lis = new ArrayList<>();if (arr.length == 1) {System.out.println(1);}// Explore both possibilities for the first index.sol2(arr, 0, lis, true);sol2(arr, 0, lis, false);System.out.println(an);}// Generates different selections using recursion.public static void sol2(int[] arr,int ind,List<Integer> lis,boolean boo) {// All indices have been processed.if (ind == arr.length) {// Check whether this selection is good// and has not already been counted.if (!msl.contains(lis) && ch2(lis, arr)) {an++;// Store a copy because the original list// continues changing during backtracking.msl.add(new ArrayList<>(lis));System.out.println(lis);}return;}// Check the current selection as well.if (!msl.contains(lis) && ch2(lis, arr)) {an++;msl.add(new ArrayList<>(lis));System.out.println(lis);}// Include the current index.if (boo) {lis.add(ind);}// Continue recursively.sol2(arr, ind + 1, lis, true);// Backtrack and remove the last selected index.if (lis.size() != 0) {lis.remove(lis.size() - 1);}// Explore the branch where the current index// is not selected.sol2(arr, ind + 1, lis, false);}}Dry RunFor:[1, 2, 3, 4, 0, 5]Suppose the selected indices are:[4]Index 4 contains 0.Removing it gives:[1, 2, 3, 4, 5]This is strictly increasing.Therefore:[0]is counted.Now consider:[3, 4]Removing indices 2 and 3 gives:[1, 2, 0, 5]Since:2 > 0the remaining array is not increasing.Therefore, this candidate is rejected.Another candidate:[2, 3, 4]removes:[3, 4, 0]and leaves:[1, 2, 5]which is strictly increasing.So this candidate is counted.The recursion continues until all possible selections have been explored.Important Detail: Subarray vs SubsetThere is an important distinction worth understanding when reviewing this implementation.The problem asks for a subarray, which means the removed elements must be contiguous.For example:[2, 3, 4]is a subarray.But:[2, 4]is not a subarray if the original array contains another element between them.The recursive code, however, chooses individual indices independently. Therefore, it explores subsets of indices rather than explicitly restricting the selection to contiguous ranges.This is an important conceptual difference.For a production or interview solution, the recursion should be changed to work directly with:left indexright indexso that only contiguous removals are considered.Why This Approach Is Not Suitable for n = 10⁵For every index, the recursion can make two choices:includeexcludeThis creates approximately:2ⁿpossible selections.Furthermore, each candidate is checked by constructing another array and scanning it.Therefore, the brute-force approach grows exponentially and cannot handle:n = 100000efficiently.This makes the problem much more interesting: the real challenge is finding the structure that allows the count to be obtained without examining every possible subarray individually.Toward an Optimized SolutionA useful way to analyze the problem is to split the remaining array into two parts.After removing arr[l...r], the remaining array is:arr[0...l-1] + arr[r+1...n-1]For this combined array to be strictly increasing, three things must be true:Left part must be increasingarr[0...l-1]must already be strictly increasing.Right part must be increasingarr[r+1...n-1]must already be strictly increasing.The two parts must connectIf both parts exist:arr[l-1] < arr[r+1]must hold.This observation removes the need to construct the remaining array for every candidate.The Main PatternThe problem can therefore be viewed as:Increasing Prefix|| removed subarray↓Increasing SuffixThe only difficult part is determining whether the last element of the prefix can connect to the first element of the suffix.This is the key observation that leads from brute force toward an efficient two-pointer/prefix-suffix based solution.Complexity of the Provided SolutionThe recursive generation can explore up to:O(2ⁿ)different index selections.For every candidate, ch2() may also scan the entire array.Therefore, the overall worst-case complexity is approximately:O(n × 2ⁿ)with substantial additional memory for the recursion and stored selections.This is only practical for very small arrays and should be considered a brute-force exploration, not a solution for the stated n = 10⁵ constraint.Interview TakeawayThis problem teaches an important DSA lesson:Before optimizing code, identify exactly what the problem is asking for.There is a significant difference between:subsetand:subarrayA subset can select arbitrary indices, while a subarray must be contiguous.Once the problem is represented correctly, the next question becomes:What must be true about the array remaining after removing [l...r]?That leads directly to the prefix/suffix observation:Left side increasing+Right side increasing+Left boundary < Right boundaryThis type of transformation is often much more valuable in an OA than trying to optimize an exponential recursion line by line.ConclusionThis Apple OA-style problem combines subarray reasoning, recursion, and array properties in an interesting way.The provided solution takes a brute-force route by recursively exploring possible index selections and checking whether the remaining elements form a strictly increasing sequence.Although this approach is useful for understanding the problem and verifying small test cases, the constraint of 10⁵ requires a much more efficient strategy.The major insight is to stop thinking about the removed portion itself and instead analyze the increasing prefix and increasing suffix that remain after the removal.That shift in perspective turns an exponential search problem into one that can be approached using prefix/suffix preprocessing and two-pointer techniques.

Apple OAArraysSubarraysRecursionBacktrackingHashSetBrute ForceJavaContignous Array