LogoKode$word

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

An interesting subarray-removal problem where the remaining elements must form a strictly increasing array.

Krishna Shrivastava
6 views
LinkedInGithubX
0
0
Apple OAArraysSubarraysRecursionBacktrackingHashSetBrute ForceJavaContignous Array
Count the Number of Good Subarrays – Apple OA DSA Problem & Java Solution
Listen to articleAudio version
Ad

Introduction

This 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 Statement

Given 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.

Constraints

1 ≤ n ≤ 10⁵

-10⁹ ≤ arr[i] ≤ 10⁹

Example

Consider:

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 = 10

Key Observation

The array:

[1, 2, 3, 4, 0, 5]

is already strictly increasing except around:

4 → 0

Removing 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 Approach

A straightforward way to explore the problem is to generate possible selections of indices using recursion.

The recursive function maintains:

curr

which contains the indices currently selected for removal.

For every index, there are two choices:

  1. Include the index in the selected set.
  2. 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 Candidate

The 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 Solution

The 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 Run

For:

[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 > 0

the 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 Subset

There 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 index
right index

so that only contiguous removals are considered.

Why This Approach Is Not Suitable for n = 10⁵

For every index, the recursion can make two choices:

include
exclude

This 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 = 100000

efficiently.

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 Solution

A 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 increasing

arr[0...l-1]

must already be strictly increasing.

Right part must be increasing

arr[r+1...n-1]

must already be strictly increasing.

The two parts must connect

If 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 Pattern

The problem can therefore be viewed as:

Increasing Prefix
|
| removed subarray
↓
Increasing Suffix

The 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 Solution

The 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 Takeaway

This problem teaches an important DSA lesson:

Before optimizing code, identify exactly what the problem is asking for.

There is a significant difference between:

subset

and:

subarray

A 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 boundary

This type of transformation is often much more valuable in an OA than trying to optimize an exponential recursion line by line.

Conclusion

This 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.

Related Articles

Recursion in Java - Complete Guide With Examples and Practice Problems

Recursion in Java - Complete Guide With Examples and Practice Problems

Learn recursion in Java from scratch. Includes how recursion works, base case, recursive case, types of recursion, dry runs, time & space complexity, and top LeetCode problems with solutions.

Read Article
Longest Subarray of 1's After Deleting One Element – Sliding Window Approach

Longest Subarray of 1's After Deleting One Element – Sliding Window Approach

Learn how to maximize consecutive 1's in a binary array by deleting exactly one element using an efficient sliding window technique.

Read Article
Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

Learn how to solve the Subsets problem using recursion, backtracking, loops, and bit manipulation. Includes Java code, intuition, and complexity analysis.

Read Article
LeetCode 3689: Maximum Total Subarray Value I – Java Greedy Solution Explained

LeetCode 3689: Maximum Total Subarray Value I – Java Greedy Solution Explained

Learn how to solve LeetCode 3689 using an efficient greedy approach in Java. Understand the intuition, dry run, complexity analysis, and why the maximum subarray value can be reused k times for the optimal solution.

Read Article
Ai Assistant Kas