medium Maximum Length of Semi-Decreasing Subarrays

Problem Statement

Given an integer array nums, return the length of the longest semi-decreasing subarray of nums, or 0 if there are no such subarrays.

If the first element is strictly greater than its last element for any array, it is semi-decreasing.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

• Example 1:

  • Input: nums = [8, 4, 5, 3, 2]
  • Expected Output: 5
  • Justification: The entire array is the largest segment where the first element (8) is greater than the last (2).

• Example 2:

  • Input: nums = [1, 2, 3, 4, 5]
  • Expected Output: 0
  • Justification: There's no segment where the starting number is greater than the ending number.

• Example 3:

  • Input: nums = [1, 2, 12, 2, 5, 11, 13]
  • Expected Output: 4
  • Justification: The largest semi-decreasing subarray is [12, 2, 5, 11].

Solution

To solve this problem, we adopt a straightforward yet effective approach by examining all possible contiguous subarrays within the given array to identify those that meet the specific criterion of being semi-decreasing. This means we look for segments where the starting element is strictly greater than the ending element, without imposing restrictions on the sequence's behavior between these two points. Through meticulous iteration, starting from each element and comparing it with subsequent elements, we ensure no potential solution is overlooked.

This exhaustive method, while simple, leverages the power of brute force to methodically parse through the array, ensuring that the maximum length of any such semi-decreasing subarray is captured accurately. By evaluating each segment's starting and ending points against our criteria, we pinpoint the longest segment that fulfills the condition, thus arriving at the solution.

Step-by-step Algorithm

1. Initialize Variables:

   • Start with a variable maxLength set to 0, which will hold the maximum length of a semi-decreasing subarray found.
   • Use two nested loops with indices i and j to iterate through the array, where i starts from 0 and j starts from i + 1.

2. Iterate Through the Array:

   • The outer loop runs through each element of the array, treating each element as a potential starting point of a semi-decreasing subarray.
   • The inner loop runs from the next element after i to the end of the array, considering each as a potential end of a semi-decreasing subarray starting at i.

3. Check for Semi-Decreasing Subarray:

   • Within the inner loop, check if the element at the start of the subarray (index i) is greater than the element at the current end of the subarray (index j). This checks the condition for a subarray being semi-decreasing.

4. Update Maximum Length:

   • If the condition in step 3 is true, calculate the length of the current subarray (j - i + 1) and compare it with maxLength.
   • Update maxLength if the current subarray's length is greater.

5. Return Result:

   • After the loops complete, return the value of maxLength, which now contains the length of the longest semi-decreasing subarray found.

Algorithm Walkthrough

Let's consider the Input: nums = [1, 2, 12, 2, 5, 11, 13].

1. Initialization:

   • maxLength is initialized to 0. This variable will store the length of the longest semi-decreasing subarray found.

2. Iterate with i=0 (nums[i]=1):

   • Iterate j from 1 to the end of the array. Since nums[0] is less than all other elements (due to the increasing order at the beginning), no j will satisfy nums[i] > nums[j] for this round.

3. Iterate with i=1 (nums[i]=2):

   • Similarly, nums[1] is less than all elements to its right, so again, no j will satisfy the condition for this i.

4. Iterate with i=2 (nums[i]=12):

   • For j=3 (nums[j]=2): The condition is satisfied. Calculate tempLength = 2. Update maxLength = 2..
   • For j=4 (nums[j]=5): The condition is satisfied. Calculate tempLength = 3. Update maxLength = 3..
   • For j=5 (nums[j]=11): The condition is satisfied. Calculate tempLength = 4, update maxLength to 4.
   • For j=6 (nums[j]=13): The condition is not satisfied. No update to maxLength.

5. Iterate with i=3 (nums[i]=2):

   • All subsequent j values for this i do not satisfy nums[i] > nums[j] because nums[i] is one of the smallest.

6. Iterate with i=4 (nums[i]=5):

   • The process is similar to previous steps, with no updates to maxLength due to the condition not being met or finding shorter lengths than currently stored in maxLength.

7. Iterate with i=5 (nums[i]=11):

   • For j=6 (nums[j]=13): The condition is not satisfied. No update to maxLength.

8. Conclusion:

   • The iteration ends with maxLength = 4, representing the longest semi-decreasing subarray [12, 2, 5, 11].

Code

public class Solution {

  public int findMaxLength(int[] nums) {
    // Initialize variables to track the maximum length
    int maxLength = 0, tempLength, n = nums.length;

    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        // Check if the current segment meets the criteria
        if (nums[i] > nums[j]) {
          tempLength = j - i + 1;
          maxLength = Math.max(maxLength, tempLength);
        }
      }
    }
    return maxLength;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Example 1
    System.out.println(sol.findMaxLength(new int[] { 8, 4, 5, 3, 2 }));

    // Example 2
    System.out.println(sol.findMaxLength(new int[] { 1, 2, 3, 4, 5 }));

    // Example 3
    System.out.println(sol.findMaxLength(new int[] { 1, 2, 12, 2, 5, 11, 13 }));
  }
}

Complexity Analysis

Time Complexity:

The nested loops iterate over each pair of elements in the array to check every possible subarray. Therefore, the time complexity is quadratic in the number of elements, n, in the input array.

Space Complexity:

Only a constant amount of extra space is used (variables for storing indices, lengths, and the maximum length found), so the space complexity is constant.

Optimized Solution

To solve this problem, we use a monotonic stack to efficiently find the maximum length of a semi-decreasing subarray. The idea is to track indices of elements in increasing order in the stack. Then, by traversing the array from right to left, we check where each element forms a semi-decreasing subarray. If an element is smaller than the element at the top of the stack, it means we have found a decreasing pattern, and we compute the subarray length.

This approach ensures that each index is pushed and popped at most once, leading to an time complexity. Instead of checking every subarray individually, which would be inefficient ( or worse), we leverage the stack to track potential subarray start points in a single pass, then efficiently compute the maximum subarray length in a second pass.

Step-by-Step Algorithm

1. Initialize Required Variables:

   • Create an empty monotonic stack to store indices.
   • Store the length of the array in a variable n.
   • Initialize maxLength = 0 to keep track of the maximum subarray length.

2. First Pass (Building the Stack - Left to Right):

   • Iterate through the array from index 0 to n - 1.
   • For each element:
     • If the stack is empty or the current element is greater than the element at the top index, push its index onto the stack.
     • This ensures the stack maintains indices in increasing order, which helps in identifying valid decreasing subarrays later.

3. Second Pass (Finding Maximum Subarray - Right to Left):

   • Traverse the array from right to left (index n - 1 to 0).
   • For each element:
     • While the stack is not empty and the element at the top of the stack is greater than the current element, perform the following:
       • Compute the subarray length as (i - stack.peek() + 1).
       • Update maxLength if the computed subarray length is greater than its current value.
       • Pop the top element from the stack.
     • This ensures that we correctly determine the longest subarray where the first element is greater than the last, creating a valid semi-decreasing sequence.

4. Return the Final Result:

   • After completing both passes, return the maximum subarray length stored in maxLength.

Algorithm Walkthrough

Input: [1, 2, 12, 2, 5, 11, 13]

1. Initialization

• Input Array: [1, 2, 12, 2, 5, 11, 13]
• Stack: [] (empty initially)
• maxLength: 0
• n: 7

2. First Pass – Building the Stack (Left to Right)

• Iteration 1 (i = 0):
  • nums[0] = 1
  • Stack is empty → Push index 0.
  • Stack becomes: [0]
• Iteration 2 (i = 1):
  • nums[1] = 2
  • Top index is 0 with nums[0] = 1 which is less than 2 → Push index 1.
  • Stack becomes: [0, 1]
• Iteration 3 (i = 2):
  • nums[2] = 12
  • Top index is 1 with nums[1] = 2 (2 < 12) → Push index 2.
  • Stack becomes: [0, 1, 2]
• Iteration 4 (i = 3):
  • nums[3] = 2
  • Top index is 2 with nums[2] = 12 (12 > 2) → Do not push.
  • Stack remains: [0, 1, 2]
• Iteration 5 (i = 4):
  • nums[4] = 5
  • Top index is still 2 with nums[2] = 12 (12 > 5) → Do not push.
  • Stack remains: [0, 1, 2]
• Iteration 6 (i = 5):
  • nums[5] = 11
  • Top index is still 2 with nums[2] = 12 (12 > 11) → Do not push.
  • Stack remains: [0, 1, 2]
• Iteration 7 (i = 6):
  • nums[6] = 13
  • Top index is 2 with nums[2] = 12 (12 < 13) → Push index 6.
  • Stack becomes: [0, 1, 2, 6]

3. Second Pass – Calculating Maximum Subarray Length (Right to Left)

We now traverse from right to left. For each index i, we repeatedly check if the element at the top of the stack is greater than nums[i]. If so, we compute the subarray length using that index and then pop it off.

• Iteration 1 (i = 6):
  • nums[6] = 13
  • Stack Top: Index 6 → nums[6] = 13 is not greater than nums[6] (they are equal).
  • No pop occurs.
  • Stack remains: [0, 1, 2, 6]
• Iteration 2 (i = 5):
  • nums[5] = 11
  • Stack Top: Index 6 → nums[6] = 13 is greater than 11.
    • Calculate subarray length:
      • Use i (5) and stack top (6):
      • Length = i - stack.peek() + 1 = 5 - 6 + 1 = 0
    • Update: maxLength remains 0.
    • Pop index 6.
  • Stack becomes: [0, 1, 2]
  • While Loop Check Again:
    • Now, top is index 2 → nums[2] = 12 is greater than 11.
    • Calculate subarray length:
      • Length = 5 - 2 + 1 = 4
    • Update: maxLength becomes 4.
    • Pop index 2.
  • Stack becomes: [0, 1]
  • While Loop Ends:
    • Now, top is index 1 with nums[1] = 2 which is not greater than 11.
• Iteration 3 (i = 4):
  • nums[4] = 5
  • Stack Top: Index 1 → nums[1] = 2 (2 is not greater than 5).
  • No pop occurs.
  • Stack remains: [0, 1]
• Iteration 4 (i = 3):
  • nums[3] = 2
  • Stack Top: Index 1 → nums[1] = 2 is not greater than 2 (equal).
  • No pop occurs.
  • Stack remains: [0, 1]
• Iteration 5 (i = 2):
  • nums[2] = 12
  • Stack Top: Index 1 → nums[1] = 2 is not greater than 12.
  • No pop occurs.
  • Stack remains: [0, 1]
• Iteration 6 (i = 1):
  • nums[1] = 2
  • Stack Top: Index 1 itself, so nothing to compare.
  • No pop occurs.
  • Stack remains: [0, 1]
• Iteration 7 (i = 0):
  • nums[0] = 1
  • Stack Top: Index 1 → nums[1] = 2 is greater than 1.
    • Calculate subarray length:
      • Length = 0 - 1 + 1 = 0
    • maxLength remains: 4.
    • Pop index 1.
  • Stack becomes: [0]
  • While Loop Check Again:
    • Now, top is index 0 → nums[0] = 1 is not greater than 1.
  • While Loop Ends.
  • Stack remains: [0]

4. Final Output

• Final maxLength: 4
• Thus, the maximum length of a semi-decreasing subarray for the array [1, 2, 12, 2, 5, 11, 13] is 4.

Code

import java.util.Stack;

class Solution {

  public int findMaxLength(int[] nums) {
    Stack<Integer> stack = new Stack<>(); // Monotonic stack to track indices
    int n = nums.length;

    // First pass: Build a stack with indices of elements in increasing order
    for (int i = 0; i < n; i++) {
      // Push index onto stack if it's empty or the current element is greater than the top element
      if (stack.isEmpty() || nums[stack.peek()] < nums[i]) {
        stack.push(i);
      }
    }

    int maxLength = 0;

    // Second pass: Traverse the array from the end to calculate the max subarray length
    for (int i = n - 1; i >= 0; i--) {
      // If the top of the stack is greater than the current element, calculate length
      while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
        maxLength = Math.max(maxLength, i - stack.peek() + 1);
        stack.pop(); // Remove the top index as it's processed
      }
    }

    return maxLength;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Example 1
    System.out.println(sol.findMaxLength(new int[] { 8, 4, 5, 3, 2 })); // Expected output: 5

    // Example 2
    System.out.println(sol.findMaxLength(new int[] { 1, 2, 3, 4, 5 })); // Expected output: 0

    // Example 3
    System.out.println(sol.findMaxLength(new int[] { 1, 2, 12, 2, 5, 11, 13 })); // Expected output: 4
  }
}

Complexity Analysis

Time Complexity Analysis

1. First Pass (Building the Stack) →

   • We iterate over the array from left to right (i = 0 to n-1).
   • Each element is pushed onto the stack at most once.
   • Total operations: .

2. Second Pass (Finding Maximum Subarray Length) →

   • We iterate over the array from right to left (i = n-1 to 0).
   • Each element is popped from the stack at most once.
   • Total operations: .

Since both passes run in independently, the overall time complexity is:
.

Space Complexity Analysis

1. Stack Storage →
   • In the worst case, the stack may store all n indices (e.g., when elements are strictly increasing).
   • Space used by the stack: .
2. Other Variables →
   • The algorithm uses a few integer variables (maxLength, n, loop counters), which require constant space.

Thus, the overall space complexity is due to the stack storage.