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.