algoadvance

Leetcode 665. Non

Problem Statement

You are given an integer array nums with n elements. A subarray of nums is called good if its length is at least 2 and its elements are non-decreasing. Return the length of the shortest good subarray of nums. If no such subarray exists, return -1.

Clarifying Questions

1. What constitutes a non-decreasing array? A subarray is non-decreasing if for any two indices i and j within the subarray where i < j, nums[i] <= nums[j].

2. What is the minimal and maximal length for the input array nums? The input will adhere to the constraint n >= 1.

3. What should be returned if the input array has only one element? Return -1 since a subarray of length 1 cannot be considered.

4. Are there any constraints on the elements of nums? Elements of nums can be any integer within the bounds of typical integer ranges.

Strategy

1. Iterate over the array, maintaining two pointers i and j where i denotes the start of a potential subarray and j scans the elements ahead to find the longest non-decreasing sequence starting from i.

2. Whenever a non-decreasing condition is broken (nums[j] < nums[j-1]), calculate the length of the subarray from i to j-1. Update the minimum length if this subarray meets the criteria of having at least 2 elements.

3. Continue this process until the end of the array is reached.

4. If no valid subarray is found by the end of the iteration, return -1.

The approach ensures we find the shortest non-decreasing subarray efficiently using a single pass over the array.

Code

public int shortestNonDecreasingSubarray(int[] nums) {
    int n = nums.length;
    if (n < 2) return -1; // No subarray can exist in this case.

    int minLength = Integer.MAX_VALUE;
    int i = 0;

    // Iterate through the array.
    while (i < n) {
        int j = i + 1;
        // Find the end of a non-decreasing subarray.
        while (j < n && nums[j] >= nums[j - 1]) {
            j++;
        }
        // Calculate the length of the subarray.
        int length = j - i;
        if (length >= 2) {
            minLength = Math.min(minLength, length);
        }
        i = j; // Move to the next starting point.
    }

    return (minLength == Integer.MAX_VALUE) ? -1 : minLength;
}

Time Complexity

• Time Complexity: (O(n)) - The array is traversed only once with the increment of i and j.
• Space Complexity: (O(1)) - Only a few extra variables are used regardless of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?