Leetcode – Three Consecutive Odds Solution

Finding patterns in sequences or arrays is a recurring theme in algorithmic problems. The “Three Consecutive Odds” problem on Leetcode tests your ability to understand and manipulate arrays. This problem may appear simple on the surface, but it offers a chance to learn some best practices for solving array-based challenges efficiently. This article will provide a comprehensive overview of different approaches to solve the problem, including their time and space complexities.

Problem Statement

The task is to determine whether a given array contains three consecutive odd numbers. Specifically, you are given an integer array arr, and you have to return True if the array has three consecutive odd numbers; otherwise, return False.

Example:

• Input: [1, 2, 34, 3, 4, 5, 7, 23, 12]
• Output: True

In this example, [5, 7, 23] form three consecutive odd numbers in the array.

Naive Approach: Linear Traversal

Algorithm

1. Start by iterating through the array.
2. Keep a counter to track the count of consecutive odd numbers.
3. Reset the counter if an even number is found.
4. Return True if the counter reaches 3; otherwise, return False.

Here’s a Python implementation of the naive approach:

def threeConsecutiveOdds(arr):
    count = 0
    for num in arr:
        if num % 2 != 0:
            count += 1
            if count == 3:
                return True
        else:
            count = 0
    return False

Time Complexity

The time complexity is O(n), where n is the length of the array.

Space Complexity

The space complexity is O(1), as we are using only a constant amount of extra space.

Optimized Approach: Early Termination

Algorithm

1. Iterate through the array.
2. If you find an odd number, look ahead to see if the next two numbers are also odd.
3. If they are, return True.
4. If you reach the end of the array without finding three consecutive odd numbers, return False.

Here’s a Python implementation of the optimized approach:

def threeConsecutiveOdds(arr):
    n = len(arr)
    for i in range(n - 2):
        if arr[i] % 2 != 0 and arr[i+1] % 2 != 0 and arr[i+2] % 2 != 0:
            return True
    return False

Time Complexity

The time complexity is O(n), but with fewer iterations compared to the naive approach.

Space Complexity

The space complexity is O(1), as no additional memory is used.

Analyzing Both Approaches

Conclusion

The “Three Consecutive Odds” problem serves as a straightforward example to learn how to manipulate and analyze arrays. It demonstrates how small optimizations can make a noticeable difference, even if the complexity class doesn’t change. Both the naive and optimized approaches are valid solutions, but the optimized approach performs fewer iterations.