Count Strictly Increasing Subarrays

Count Strictly Increasing Subarrays

What is this problem about?

The "Count Strictly Increasing Subarrays interview question" is an array counting task. You are given an array of integers and need to find the total number of subarrays that are strictly increasing (each element is strictly greater than the one before it). For example, in [1, 3, 2], the strictly increasing subarrays are [1], [3], [2], [1, 3].

Why is this asked in interviews?

Companies like J.P. Morgan use the "Count Strictly Increasing Subarrays coding problem" to evaluate a candidate's ability to use "Dynamic Programming" or a single-pass greedy approach. It’s a test of whether you can recognize that contiguous segments with a property can be counted using a simple arithmetic formula.

Algorithmic pattern used

This problem follows the Linear Scan and Combinatorics pattern.

1. Identify Segments: Find the lengths of contiguous segments that are strictly increasing.
2. Counting Rule: If a segment has length $L$, the total number of its subarrays is $\frac{L imes (L + 1)}{2}$.
3. Implementation:
   • Iterate through the array.
   • Maintain a counter current_length.
   • If arr[i] > arr[i-1], increment the counter.
   • If not, the current segment has ended. Reset the counter to 1.
   • Add the current_length to your total result at each step (this is a shortcut for the formula).

Example explanation

Array: [1, 2, 3]

• i=0: length=1. Total = 1. Subarray: [1].
• i=1: 2 > 1. length=2. Total = 1 + 2 = 3. Subarrays: [2], [1, 2].
• i=2: 3 > 2. length=3. Total = 3 + 3 = 6. Subarrays: [3], [2, 3], [1, 2, 3]. Total: 6.

Common mistakes candidates make

• $O(N^2)$ Brute Force: Checking every possible subarray, which is too slow for large arrays.
• Strict vs. Non-decreasing: Forgetting that "strictly increasing" means arr[i] > arr[i-1], not $\geq$.
• Off-by-one: Mistakes in resetting the length counter when a decrease is found.

Interview preparation tip

When counting contiguous subarrays with a specific property, always ask: "Does adding an element to a valid segment of length $L$ create exactly $L+1$ new valid subarrays?" If yes, a single pass with a running total is the optimal "Array interview pattern" approach.