LeetCode 1550 - Three Consecutive Odds

This problem asks us to examine a list of integers, arr, and determine whether there exists a sequence of three consecut

leetcodeeasyarray

LeetCode Problem 1550

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

This problem asks us to examine a list of integers, arr, and determine whether there exists a sequence of three consecutive odd numbers anywhere in the array. In simpler terms, we need to scan the array from left to right and check if at any point three numbers in a row are all odd. If such a sequence exists, we return true; otherwise, we return false.

The input is a one-dimensional integer array with values ranging from 1 to 1000, and the length of the array is between 1 and 1000. The output is a Boolean value. Important observations include that the array is guaranteed to be non-empty and small enough (up to 1000 elements) that simple linear scans are feasible.

Potential edge cases include arrays that are shorter than three elements (where the answer must be false), arrays with exactly three elements, arrays with all even numbers, or arrays with alternating even and odd numbers. We also must ensure that we correctly handle the first and last elements when checking for consecutive odd sequences.

Approaches

The brute-force approach involves checking every possible consecutive triplet in the array. For each index i, we would check if arr[i], arr[i+1], and arr[i+2] are all odd. This approach works because it exhaustively verifies all possible three-element windows. For arrays of length n, this requires n-2 checks.

The optimal approach leverages a simple linear scan with a counter. As we iterate through the array, we maintain a running count of consecutive odd numbers. Each time we encounter an odd number, we increment the counter; if we encounter an even number, we reset the counter to zero. If the counter reaches 3 at any point, we immediately return true. This is more elegant because it only requires a single pass through the array and minimal extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Checks all triplets explicitly, slightly more verbose
Optimal O(n) O(1) Uses a running counter to track consecutive odds

Algorithm Walkthrough

  1. Initialize a counter variable consecutive_odds to 0. This will keep track of the number of consecutive odd numbers seen so far.
  2. Iterate over each number num in the array arr.
  3. For each num, check if it is odd using num % 2 != 0.
  4. If num is odd, increment consecutive_odds by 1. Otherwise, reset consecutive_odds to 0.
  5. After updating the counter, check if consecutive_odds has reached 3. If it has, immediately return true because we have found three consecutive odd numbers.
  6. If the loop finishes without the counter reaching 3, return false.

Why it works: The counter ensures we always have the exact number of consecutive odd numbers. Resetting on even numbers guarantees that only sequences of consecutive odd numbers are counted, and returning immediately when the counter reaches 3 ensures correctness and efficiency.

Python Solution

from typing import List

class Solution:
    def threeConsecutiveOdds(self, arr: List[int]) -> bool:
        consecutive_odds = 0
        for num in arr:
            if num % 2 != 0:
                consecutive_odds += 1
                if consecutive_odds == 3:
                    return True
            else:
                consecutive_odds = 0
        return False

The Python solution initializes a counter to track consecutive odd numbers. As it iterates through the array, it increments the counter for odd numbers and resets it for even numbers. Once the counter reaches three, it immediately returns true. If the iteration completes without finding three consecutive odds, it returns false. This follows the algorithm exactly.

Go Solution

func threeConsecutiveOdds(arr []int) bool {
    consecutiveOdds := 0
    for _, num := range arr {
        if num % 2 != 0 {
            consecutiveOdds++
            if consecutiveOdds == 3 {
                return true
            }
        } else {
            consecutiveOdds = 0
        }
    }
    return false
}

The Go solution mirrors the Python approach. It uses an integer counter to track consecutive odd numbers, iterating through the slice. The main differences are syntax and range iteration. No special handling for nil slices is needed because the problem guarantees at least one element.

Worked Examples

Example 1: arr = [2,6,4,1]

Step num consecutive_odds Action
1 2 0 even, reset counter
2 6 0 even, reset counter
3 4 0 even, reset counter
4 1 1 odd, increment counter

Final counter never reaches 3, return false.

Example 2: arr = [1,2,34,3,4,5,7,23,12]

Step num consecutive_odds Action
1 1 1 odd
2 2 0 even
3 34 0 even
4 3 1 odd
5 4 0 even
6 5 1 odd
7 7 2 odd
8 23 3 odd -> return true

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through the array once, performing constant-time operations per element
Space O(1) Only a single counter is used, no additional data structures

The linear scan guarantees that each element is processed exactly once, and the counter uses negligible memory regardless of array size.

Test Cases

# Provided examples
assert Solution().threeConsecutiveOdds([2,6,4,1]) == False  # no consecutive odds
assert Solution().threeConsecutiveOdds([1,2,34,3,4,5,7,23,12]) == True  # sequence [5,7,23]

# Edge cases
assert Solution().threeConsecutiveOdds([1]) == False  # single element
assert Solution().threeConsecutiveOdds([1,3]) == False  # two elements, both odd
assert Solution().threeConsecutiveOdds([1,3,5]) == True  # exactly three odd elements
assert Solution().threeConsecutiveOdds([2,4,6,8]) == False  # all even
assert Solution().threeConsecutiveOdds([1,1,2,1,1,1]) == True  # sequence at end
assert Solution().threeConsecutiveOdds([1,1,1,2,1,1]) == True  # sequence at start
assert Solution().threeConsecutiveOdds([2,1,3,5,2]) == True  # sequence in middle
Test Why
[2,6,4,1] Checks array with no consecutive odds
[1,2,34,3,4,5,7,23,12] Checks typical case with a sequence in the middle
[1] Single element, too short
[1,3] Two elements, cannot form a triplet
[1,3,5] Exactly three consecutive odds
[2,4,6,8] All even numbers
[1,1,2,1,1,1] Sequence at end of array
[1,1,1,2,1,1] Sequence at start of array
[2,1,3,5,2] Sequence in the middle of array

Edge Cases

Short arrays: Arrays with fewer than three elements cannot contain three consecutive odd numbers. The implementation correctly returns false in these cases by never reaching a counter of three.

Sequence at the boundaries: If the sequence of three consecutive odds occurs at the beginning or end of the array, the algorithm still works because it checks each element in order and updates the counter dynamically. No special handling for boundaries is needed.

Alternating odd and even numbers: In arrays where odd and even numbers alternate frequently, the counter resets each time an even number is encountered. This ensures that only true consecutive sequences are counted, preventing false positives.

This solution is efficient, handles all edge cases, and clearly implements the required logic in both Python and Go.