Scale Engineer

Three Consecutive Odds

Easy
#1427Time: 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: O(1), as we don't use any extra space that scales with the input size.
Data structures
Array

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1), as we don't use any extra space that scales with the input size.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem