Problem Description

The "Three Consecutive Odds" problem asks you to determine whether a given list of integers contains any three consecutive numbers that are all odd. Given an array arr, your task is to return True if there exists at least one set of three adjacent elements in arr such that all three are odd numbers. Otherwise, return False.

• Each element in arr is an integer.
• Three numbers are considered consecutive if they appear next to each other in the array (i.e., at indices i, i+1, and i+2).
• You must not reuse elements; only strictly consecutive elements are allowed.
• Return True as soon as you find such a triplet; otherwise, return False after checking the entire array.

Thought Process

To solve this problem, let's first consider a straightforward approach: for every group of three consecutive elements in the array, check if all of them are odd. If any such group exists, we can immediately return True. If we reach the end of the array without finding such a group, we return False.

The brute-force method would involve iterating through every possible triplet of consecutive elements and checking their parity. However, since we only need to check consecutive elements, we can do this efficiently with a single loop.

There's no need for extra data structures or complex logic, as the problem is localized to checking each window of three numbers as we scan the array. This is much simpler than, for example, finding any three odd numbers anywhere in the array.

Solution Approach

Let's break down the steps to solve this problem:

1. Iterate through the array: Start from the first element and stop at the third-to-last element (since we need groups of three).
2. Check each triplet: For each index i, check if arr[i], arr[i+1], and arr[i+2] are all odd numbers. An integer is odd if num % 2 != 0.
3. Early exit: If you find a triplet where all three numbers are odd, return True immediately.
4. Return False if none found: If the loop finishes without finding any such triplet, return False.

This approach is optimal for the problem, as it only requires a single pass through the array and constant extra space.

Example Walkthrough

Let's consider the sample input arr = [2, 6, 4, 1, 3, 5, 9].

• Start at index 0: [2, 6, 4] → 2 is even, skip.
• Next, index 1: [6, 4, 1] → 6 is even, skip.
• Next, index 2: [4, 1, 3] → 4 is even, skip.
• Next, index 3: [1, 3, 5] → 1 is odd, 3 is odd, 5 is odd. All are odd!

Since we've found three consecutive odd numbers at indices 3, 4, and 5, we return True immediately.

Code Implementation

class Solution:
    def threeConsecutiveOdds(self, arr):
        for i in range(len(arr) - 2):
            if arr[i] % 2 == 1 and arr[i+1] % 2 == 1 and arr[i+2] % 2 == 1:
                return True
        return False
      

class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr) {
        for (int i = 0; i < arr.size() - 2; ++i) {
            if (arr[i] % 2 == 1 && arr[i+1] % 2 == 1 && arr[i+2] % 2 == 1)
                return true;
        }
        return false;
    }
};
      

class Solution {
    public boolean threeConsecutiveOdds(int[] arr) {
        for (int i = 0; i <= arr.length - 3; i++) {
            if (arr[i] % 2 == 1 && arr[i+1] % 2 == 1 && arr[i+2] % 2 == 1) {
                return true;
            }
        }
        return false;
    }
}
      

var threeConsecutiveOdds = function(arr) {
    for (let i = 0; i <= arr.length - 3; i++) {
        if (arr[i] % 2 === 1 && arr[i+1] % 2 === 1 && arr[i+2] % 2 === 1) {
            return true;
        }
    }
    return false;
};
      

Time and Space Complexity

• Brute-force approach: Since we only need to check each group of three consecutive elements, the brute-force and optimized approaches are essentially the same for this problem. Each check is O(1), and we perform O(n) such checks, where n is the length of the array.
• Time Complexity: O(n), where n is the length of arr.
• Space Complexity: O(1), as we only use a constant amount of extra space (no additional data structures).

Summary

The "Three Consecutive Odds" problem is a great example of a localized sliding window check. By simply iterating through the array and examining each group of three consecutive numbers, we can efficiently determine if any such group contains all odd numbers. The solution is elegant in its simplicity, requiring only a single pass and no extra space, making it both easy to understand and optimal for performance.