Three Consecutive Odds

EASY

Description

Given an integer array arr, return true if there are three consecutive odd numbers in the array. Otherwise, return false.

Example 1:

Input: arr = [2,6,4,1]
Output: false
Explanation: There are no three consecutive odds.

Example 2:

Input: arr = [1,2,34,3,4,5,7,23,12]
Output: true
Explanation: [5,7,23] are three consecutive odds.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000

Approaches

Checkout 2 different approaches to solve Three Consecutive Odds. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Window Check

This approach involves iterating through the array and checking every possible contiguous window of size three. For each window, we verify if all three numbers are odd.

Algorithm

Check if the array has fewer than 3 elements. If so, return false as it's impossible to have three consecutive numbers.
Loop through the array from index i = 0 to arr.length - 3.
Inside the loop, check if arr[i], arr[i+1], and arr[i+2] are all odd using the modulo operator (%).
If all three are odd, we have found our sequence, so we return true.
If the loop finishes without finding such a sequence, we return false.

We can solve this by iterating through the array with a loop. The loop should start at index 0 and end at arr.length - 3 to ensure there are at least three elements left to check (the current one, and the next two).

In each iteration, for the current index i, we check if the number arr[i], the next number arr[i+1], and the number after that arr[i+2] are all odd.

An integer x is odd if the remainder of its division by 2 is not 0 (i.e., x % 2 != 0).

If we find a triplet (arr[i], arr[i+1], arr[i+2]) where all three are odd, we can immediately stop and return true.

If the loop finishes without finding any such triplet, it means no three consecutive odd numbers exist in the array, so we return false.

class Solution {
    public boolean threeConsecutiveOdds(int[] arr) {
        // We need at least 3 elements to have 3 consecutive odds.
        if (arr.length < 3) {
            return false;
        }

        // Iterate up to the third-to-last element.
        for (int i = 0; i <= arr.length - 3; i++) {
            // Check if the current, next, and next-next elements are all odd.
            if (arr[i] % 2 != 0 && arr[i+1] % 2 != 0 && arr[i+2] % 2 != 0) {
                return true;
            }
        }

        // If the loop completes, no such sequence was found.
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n), where `n` is the length of the array. We iterate through the array approximately `n-2` times, and each check is a constant time operation.Space Complexity: O(1), as we don't use any extra space that scales with the input size.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

In each step of the loop, we might re-check elements that were already checked in the previous step. For example, arr[i+1] and arr[i+2] in one iteration will be checked again as arr[i] and arr[i+1] in the next iteration.

Code Solutions

Checking out 3 solutions in different languages for Three Consecutive Odds. Click on different languages to view the code.

class Solution {
public
  boolean threeConsecutiveOdds(int[] arr) {
    int cnt = 0;
    for (int v : arr) {
      if (v % 2 == 1) {
        ++cnt;
      } else {
        cnt = 0;
      }
      if (cnt == 3) {
        return true;
      }
    }
    return false;
  }
}

Video Solution

Watch the video walkthrough for Three Consecutive Odds

Data Structures:

Array