Coding

Count Strictly Increasing Subarrays

Asked at

Ebay

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given an array nums consisting of positive integers.

Return the number of subarrays of nums that are in** strictly increasing** order.

A subarray is a contiguous part of an array.

Input: nums = [1,3,5,4,4,6] Output: 10 Explanation: The strictly increasing subarrays are the following:

Subarrays of length 1: [1], [3], [5], [4], [4], [6].
Subarrays of length 2: [1,3], [3,5], [4,6].
Subarrays of length 3: [1,3,5]. The total number of subarrays is 6 + 3 + 1 = 10.

Input: nums = [1,2,3,4,5] Output: 15 Explanation: Every subarray is strictly increasing. There are 15 possible subarrays that we can take.

Consider the array nums = [2, 4, 3, 5, 6]. How many** strictly increasing **subarrays can you find?

1 <= nums.length <= 105
1 <= nums[i] <= 106

cpp

class Solution {
public:
    long long countSubarrays(vector<int>& nums) {
        // Your code goes here
    }
};

java

class Solution {
    public long countSubarrays(int[] nums) {
        // Your code goes here
    }
}

python

class Solution:
    def countSubarrays(self, nums):
        # Your code goes here

javascript

class Solution {
    countSubarrays(nums) {
        // Your code goes here
    }
}

csharp

class Solution
{
    public long CountSubarrays(int[] nums)
    {
        // Your code goes here
    }
}

func countSubarrays(nums []int) int64{

}

Stuck? Show a way to structure it+

01Track the length of the current strictly increasing run.
02Extend it when `nums[i] > nums[i-1]`; otherwise reset it to one.
03Add the current run length to the answer at every index.
04Use a 64-bit accumulator because the count can be quadratic.

Reference answer

Every strictly increasing subarray ending at index i is a suffix of the current increasing run. Let run be that run's length. If nums[i] > nums[i-1], increment run; otherwise reset it to 1. Add run to the total, because there are exactly run valid increasing subarrays that end at i. For example, a run of length 3 contributes 1, then 2, then 3 across its positions. This is O(n) time and O(1) extra space. Equal neighboring values break strict increase, and the answer should use a wide integer because an all-increasing array has n(n+1)/2 subarrays.

Then expect these follow-ups

How would you count non-decreasing subarrays?
Tests: condition adaptation
How would you answer many range queries for this count?
Tests: preprocessing

Hiring now

Ebay has 217 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer - Cloud SRE
Bengaluru, India
Senior Software Engineer, Infrastructure
Dublin
Software Engineer – Cloud Platform
Dublin

Or practice this question first

Next question