2863. Maximum Length of Semi-Decreasing Subarrays
Problem Description
In this problem, we are given an array nums
consisting of integer elements. Our goal is to determine the length of the longest contiguous subarray that meets a specific criterion called "semi-decreasing." A subarray is considered semi-decreasing if it starts with an element strictly greater than the element it ends with. Additionally, we should return 0
if no such subarray exists in nums
.
To illustrate, consider the following examples:
- If
nums = [5,3,1,2,4]
, the longest semi-decreasing subarray is[5,3,1]
, and its length is 3. - In the case of
nums = [1,2,3,4,5]
, there are no semi-decreasing subarrays, so the answer is 0.
The problem is essentially asking us to find the maximum distance between the starting index of the highest element and the ending index of a lower element, ensuring that this sequence forms a subarray. We must handle this task efficiently, as the naive approach of examining every possible subarray could prove to be too slow.
Intuition
To arrive at the solution, we must track the valuable information that can help us identify semi-decreasing subarrays. Recognizing that a semi-decreasing subarray's first element must be strictly greater than its last element, we can sort the unique elements of the array in reverse (from largest to smallest) and keep track of their indices.
A Python dictionary (here d
) can be employed to store the indices of each unique element. By iterating through the array and populating this dictionary, we ensure that for each element, we have a list of all indices where it occurs.
Once this preparation is done, we can iterate over the unique elements in descending order. For each element x
, we use the last occurrence of x
(since we want to maximize the subarray's length, and a semi-decreasing subarray's last element must be lower than the first) and find the distance to the smallest index k
seen so far of elements greater than x
. This smallest index k
represents the farthest we can go to the left to start a semi-decreasing subarray that ends with the given element x
.
The intuition behind maintaining k
as the minimum index seen so far is that as we proceed with lower elements, we want to extend our subarray as much to the left as possible. ans
represents the length of the longest semi-decreasing subarray found so far, which gets updated each time we find a longer semi-decreasing subarray by subtracting k
from the last index of x
and adding 1 (to account for array indexing starting from 0).
This approach systematically constructs semi-decreasing subarrays over the original array without the need for exhaustive search, thus providing a much more efficient solution.
Learn more about Sorting patterns.
Solution Approach
The implementation of the solution uses a combination of sorting, hash maps (dictionaries in Python), and linear traversal to find the longest semi-decreasing subarray. Here's a step-by-step breakdown of the algorithm based on the provided solution code:
-
The first step is to iterate through the given array
nums
and build a hash map (d
), where the key is the element value, and the value is a list of indices at which the element occurs. This is achieved with the following line of code:for i, x in enumerate(nums): d[x].append(i)
The
enumerate
function is used to get both the index (i
) and the value (x
) during iteration. -
We introduce two variables,
ans
andk
.ans
is initialized to0
, representing the length of the longest subarray found so far, andk
is initialized toinf
(infinity), representing the lowest index seen so far for elements greater than the current one being considered. -
We sort the keys of the dictionary
d
in reverse order so we can traverse from the highest element to the lowest. This is important because we are looking for subarrays where the first element is strictly greater than the last element.for x in sorted(d, reverse=True):
-
For each element
x
(sorted from largest to smallest), we calculate the prospective length of the semi-decreasing subarray ending withx
. We achieve this by computing the distance between the last occurrence ofx
and the smallest index seen so far (k
). We add1
to this distance since the array is zero-indexed:ans = max(ans, d[x][-1] - k + 1)
-
After considering the element
x
, we updatek
to hold the smallest index which could potentially be the start of a longer semi-decreasing subarray for the next iterations:k = min(k, d[x][0])
This means for subsequent smaller elements, we have the information about how far left (to a higher element) we can extend our subarray.
By iterating through the elements in this fashion, we ensure that we are always considering semi-decreasing subarrays (since we move from larger to smaller elements), and we keep extending our reach to the left as much as possible, thus finding the length of the longest such subarray efficiently.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider the following simple array:
nums = [7, 5, 4, 6, 3]
Applying the algorithm step by step:
Step 1: Build a hash map (d
) with element values as keys and a list of their indices as values.
After the first step, d
will look like this:
d = { 7: [0], 5: [1], 4: [2], 6: [3], 3: [4] }
Step 2: Initialize ans
to 0
and k
to inf
.
ans = 0 k = inf
Step 3: Sort the keys of dictionary d
in reverse order. We get the sorted keys as [7, 6, 5, 4, 3]
.
Step 4: Iterate over the sorted keys, calculating the potential length of the semi-decreasing subarray and updating ans
:
-
For key
7
, since it's the largest element, there cannot be a semi-decreasing subarray starting with7
. But we use its index0
to update the smallest indexk
. -
Update
k
tomin(k, d[7][0])
, which will bemin(inf, 0)
sok
becomes0
. -
Now, for key
6
, its last index is3
, and the smallest index seen so far is0
. The length of the semi-decreasing subarray would be3 - 0 + 1 = 4
. Soans
becomes4
. -
Update
k
tomin(k, d[6][0])
, which will bemin(0, 3)
sok
stays0
. -
For key
5
, we calculateans = max(ans, d[5][-1] - k + 1)
, which ismax(4, 1 - 0 + 1)
andans
stays4
. -
Update
k
tomin(k, d[5][0])
, sok
remains0
. -
For key
4
, we haveans = max(ans, d[4][-1] - k + 1)
, which ismax(4, 2 - 0 + 1)
andans
stays4
. -
Update
k
tomin(k, d[4][0])
, sok
remains0
. -
Finally, for key
3
, we haveans = max(ans, d[3][-1] - k + 1)
, which ismax(4, 4 - 0 + 1)
, soans
stays4
. -
k
does not need to be updated as we have finished the iterations.
Step 5: The largest ans
we found was 4
, corresponding to the subarray [7, 5, 4, 6]
, which starts with 7
and ends with 6
.
Therefore, the length of the longest semi-decreasing subarray in nums
is 4
.
Solution Implementation
1from collections import defaultdict
2from math import inf
3
4class Solution:
5 def maxSubarrayLength(self, nums: List[int]) -> int:
6 # Initialize a dictionary to hold lists of indices for each unique number
7 index_dict = defaultdict(list)
8
9 # Populate the dictionary with indices of each number
10 for i, num in enumerate(nums):
11 index_dict[num].append(i)
12
13 # Initialize variables for the maximum subarray length and the smallest index seen so far
14 max_length, smallest_index_seen = 0, inf
15
16 # Iterate over the numbers in descending order
17 for num in sorted(index_dict, reverse=True):
18 # Update max length using the highest index of the current number
19 # and the smallest index seen so far
20 max_length = max(max_length, index_dict[num][-1] - smallest_index_seen + 1)
21 # Update the smallest index seen so far to be the lowest index of the current number
22 smallest_index_seen = min(smallest_index_seen, index_dict[num][0])
23
24 # Return the maximum computed subarray length
25 return max_length
26
1class Solution {
2 public int maxSubarrayLength(int[] nums) {
3 // TreeMap to store values in descending order and their index occurrences in list
4 TreeMap<Integer, List<Integer>> valueIndicesMap = new TreeMap<>(Comparator.reverseOrder());
5
6 // Loop through the nums array and store each number with its index
7 for (int i = 0; i < nums.length; ++i) {
8 valueIndicesMap.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
9 }
10
11 // Initialize the result for maximum subarray length (answer)
12 int answer = 0;
13
14 // Initialize a variable to hold the minimum index encountered so far
15 int minIndexSoFar = Integer.MAX_VALUE;
16
17 // Iterate through the sorted values in descending order
18 for (List<Integer> indices : valueIndicesMap.values()) {
19 // Update the answer with the maximum length found till now
20 // The length is calculated using the last occurrence index of a value
21 // minus the minimum index encountered so far plus 1
22 answer = Math.max(answer, indices.get(indices.size() - 1) - minIndexSoFar + 1);
23
24 // Update the minimum index if the first occurrence index of the current value is smaller
25 minIndexSoFar = Math.min(minIndexSoFar, indices.get(0));
26 }
27
28 // Return the maximum subarray length
29 return answer;
30 }
31}
32
1#include <vector>
2#include <map>
3#include <algorithm>
4
5class Solution {
6public:
7 int maxSubarrayLength(vector<int>& nums) {
8 // Map to store numbers and their indices, sorted in descending order of the key (number)
9 map<int, vector<int>, greater<int>> indexMap;
10
11 // Fill the indexMap with indices for each number in nums
12 for (int i = 0; i < nums.size(); ++i) {
13 indexMap[nums[i]].push_back(i);
14 }
15
16 int maxLength = 0; // Tracks the maximum subarray length found
17 int minIndexWithinMaxValue = 1 << 30; // Initialize to a very large number
18
19 // Iterate through the map starting from the largest key
20 for (auto& [num, indices] : indexMap) {
21 // Update maxLength using the distance from the current smallest index (minIndexWithinMaxValue)
22 // to the last occurrence of the current number
23 maxLength = max(maxLength, indices.back() - minIndexWithinMaxValue + 1);
24
25 // Update minIndexWithinMaxValue to the smallest index seen so far
26 minIndexWithinMaxValue = min(minIndexWithinMaxValue, indices.front());
27 }
28
29 return maxLength; // Return the maximum length found
30 }
31};
32
1// This function finds the maximum length of a subarray for an array of numbers
2// where the maximum number in the subarray is at least twice as large as all other numbers in the subarray.
3function maxSubarrayLength(nums: number[]): number {
4 // Create a map to store indices for each number in the array.
5 const indexMap: Map<number, number[]> = new Map();
6
7 // Populate the map with each number's indices.
8 for (let i = 0; i < nums.length; ++i) {
9 if (!indexMap.has(nums[i])) {
10 indexMap.set(nums[i], []);
11 }
12 indexMap.get(nums[i])!.push(i);
13 }
14
15 // Get all unique numbers from the map keys and sort them in descending order.
16 const sortedKeys = Array.from(indexMap.keys()).sort((a, b) => b - a);
17
18 // Initialize the maximum subarray length variable.
19 let maxSubarrayLength = 0;
20
21 // Initialize a variable to keep track of the smallest index seen so far.
22 let smallestIndex = Infinity;
23
24 // Iterate through the sorted keys.
25 for (const key of sortedKeys) {
26 // Get the array of indices corresponding to the current key.
27 const indices = indexMap.get(key)!;
28
29 // Calculate the subarray length where the current key is possibly the maximum
30 // and compare it with the length seen so far to keep the longest.
31 maxSubarrayLength = Math.max(maxSubarrayLength, indices.at(-1) - smallestIndex + 1);
32
33 // Update the smallestIndex with the smallest index of the current key's indices.
34 smallestIndex = Math.min(smallestIndex, indices[0]);
35 }
36
37 // Return the maximum subarray length found.
38 return maxSubarrayLength;
39}
40
Time and Space Complexity
Time Complexity
The time complexity of the code is determined by several key operations:
- Enumeration and creation of dictionary: The first for loop goes through all the entries in
nums
, thus it isO(n)
wheren
is the length ofnums
. - Sorting of dictionary keys: The keys of the dictionary are sorted in reverse order. Since the number of unique elements (keys in the dictionary) could be at most
n
, the sort operation has a complexity ofO(u log u)
whereu
is the number of unique keys, with a worst-case scenario beingO(n log n)
. - Iterating over sorted keys: This iteration potentially goes through all unique keys (at most
n
), and for each key, the complexity isO(1)
since it only accesses the first and last elements of the list of indices associated with each key.
Given these considerations, the overall time complexity is O(n log n)
due to the sorting step which is likely the bottleneck.
Space Complexity
The space complexity of the code is influenced by:
- Dictionary storage: The dictionary
d
stores lists of indices per unique numbers innums
. In the worst case, where all elements are unique, the space complexity due to the dictionary would beO(n)
. - Miscellaneous variables: Variables
ans
,k
, and the space for iteration do not depend on size ofnums
and thus contribute a constant factor.
Hence, the total space complexity is O(n)
, taking into account the space occupied by the dictionary which is the dominant term.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!