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.
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
[1, 2, 34, 3, 4, 5, 7, 23, 12]
In this example,
[5, 7, 23] form three consecutive odd numbers in the array.
Naive Approach: Linear Traversal
- Start by iterating through the array.
- Keep a counter to track the count of consecutive odd numbers.
- Reset the counter if an even number is found.
Trueif the counter reaches 3; otherwise, return
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
The time complexity is O(n), where n is the length of the array.
The space complexity is O(1), as we are using only a constant amount of extra space.
Optimized Approach: Early Termination
- Iterate through the array.
- If you find an odd number, look ahead to see if the next two numbers are also odd.
- If they are, return
- If you reach the end of the array without finding three consecutive odd numbers, return
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
The time complexity is O(n), but with fewer iterations compared to the naive approach.
The space complexity is O(1), as no additional memory is used.
Analyzing Both Approaches
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.