algoadvance

Leetcode 3206. Alternating Groups I

Problem Statement

You are given an array arr. Write a function alternatingGroups(int[] arr) that returns the length of the longest subarray where each consecutive pair of elements has alternating parity (i.e., an even number followed by an odd number or an odd number followed by an even number).

Example:

Input: [1, 2, 3, 4, 5]
Output: 5

Input: [1, 3, 5, 7, 9]
Output: 1

Input: [2, 4, 6, 8, 10]
Output: 1

Clarifying Questions

  1. Q: Can the array contain zero or negative numbers? A: Yes, the array can contain zero and negative numbers.

  2. Q: What should we return if the array is empty? A: You should return 0.

  3. Q: Can the numbers be very large or very small?
    A: Yes, the numbers can be large or small, but they fit within Java’s int range.

  4. Q: What is the expected time complexity for the solution?
    A: An efficient solution should preferably be O(n).

Strategy

  1. Initialization:
    • Initialize max_length to 1, since at minimum any single element can be considered as an alternating subarray of length 1.
    • Initialize current_length to 1 to keep track of the current streak of alternating elements.
  2. Iteration:
    • Iterate through the array starting from the second element.
    • For each element, check if it has alternating parity with the previous element.
    • If yes, increment current_length.
    • If no, update max_length if current_length is greater, and reset current_length to 1.
  3. Final Check:
    • After the loop, perform one final check to ensure max_length is the maximum length encountered.
  4. Edge Case:
    • Handle the edge case where the array length is zero by immediately returning 0.

Code

public class AlternatingGroups {
    public static int alternatingGroups(int[] arr) {
        if (arr.length == 0) return 0;
        
        int max_length = 1;         // Maximum length of alternating group found
        int current_length = 1;     // Current alternating group length

        // Iterate through the array
        for (int i = 1; i < arr.length; i++) {
            if ((arr[i] % 2 == 0 && arr[i-1] % 2 != 0) || (arr[i] % 2 != 0 && arr[i-1] % 2 == 0)) {
                current_length++;
            } else {
                max_length = Math.max(max_length, current_length);
                current_length = 1;  // Reset current length
            }
        }

        // Check one last time in case the longest alternating group is at the end of the array
        max_length = Math.max(max_length, current_length);

        return max_length;
    }

    public static void main(String[] args) {
        System.out.println(alternatingGroups(new int[]{1, 2, 3, 4, 5})); // Output: 5
        System.out.println(alternatingGroups(new int[]{1, 3, 5, 7, 9})); // Output: 1
        System.out.println(alternatingGroups(new int[]{2, 4, 6, 8, 10})); // Output: 1
        System.out.println(alternatingGroups(new int[]{1, 2, 2, 3, 4, 3})); // Output: 4
        System.out.println(alternatingGroups(new int[]{})); // Output: 0
    }
}

Time Complexity

The time complexity of this solution is O(n) where n is the number of elements in the array arr. This is because we iterate over the array once, performing constant-time operations for each element. The space complexity is O(1) as we are using a fixed amount of extra space irrespective of the input size.

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