algoadvance

Leetcode 3105. Longest Strictly Increasing or Strictly Decreasing Subarray

Problem Statement

You are given an array of integers arr. Write a function to find the length of the longest subarray which is either strictly increasing or strictly decreasing. Subarray is a contiguous part of an array.

Constraints:

The function signature in Java:

public int longestAlternatingSubarray(int[] arr);

Clarifying Questions

  1. Q: What should be the output for an array with only one element?
    • A: The longest subarray in this case would be the array itself, so the length is 1.
  2. Q: Should we consider both increasing and decreasing subarrays in one pass, or should we handle them separately?
    • A: Both strictly increasing and strictly decreasing subarrays should be considered in one pass for efficiency.

Strategy

  1. Initialize Variables:
    • Create variables to keep track of the maximal length subarray which can be incremented or decremented while traversing the array.
    • maxLength: To store the maximum length found for either increasing or decreasing subarrays.
    • increasingLength and decreasingLength: For keeping track of the lengths of currently considered strictly increasing and strictly decreasing subarrays.
  2. Traverse the Array:
    • Iterate through the array from the second element to the end. For each element:
      • If the current element is greater than the previous element, increment increasingLength and reset decreasingLength to 1.
      • If the current element is less than the previous element, increment decreasingLength and reset increasingLength to 1.
      • If the current element is equal to the previous element, reset both increasingLength and decreasingLength to 1.
    • Update maxLength with the maximum value between increasingLength, decreasingLength, and the current maxLength.
  3. Edge Cases:
    • Single element array.
    • Array where all elements are the same.

Code

Here is the Java implementation for the described strategy:

public class Solution {
    public int longestAlternatingSubarray(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        if (arr.length == 1) return 1;

        int maxLength = 1;
        int increasingLength = 1;
        int decreasingLength = 1;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1]) {
                increasingLength++;
                decreasingLength = 1;  // reset decreasingLength
            } else if (arr[i] < arr[i - 1]) {
                decreasingLength++;
                increasingLength = 1;  // reset increasingLength
            } else {
                // Element equal to the previous one, so both are reset
                increasingLength = 1;
                decreasingLength = 1;
            }
            maxLength = Math.max(maxLength, Math.max(increasingLength, decreasingLength));
        }

        return maxLength;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(solution.longestAlternatingSubarray(arr));  // Output is 5 (strictly increasing)
        
        arr = new int[] {5, 4, 3, 2, 1};
        System.out.println(solution.longestAlternatingSubarray(arr));  // Output is 5 (strictly decreasing)
        
        arr = new int[] {1, 3, 5, 4, 2};
        System.out.println(solution.longestAlternatingSubarray(arr));  // Output is 3 (either 1, 3, 5 or 5, 4, 2)
        
        arr = new int[] {1, 2, 2, 1};
        System.out.println(solution.longestAlternatingSubarray(arr));  // Output is 2 (either 1, 2)
    }
}

Time Complexity

The time complexity of this algorithm is O(n), where n is the length of the input array arr. We only traverse the array once, making comparisons and updating variables in constant time.

The space complexity is O(1), as we are using a constant amount of extra space regardless of the input size.

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