Jobs

Interviews

Discussions

Shortest Subarray With OR at Least K II

Medium

Amazon

3 views

Topics:

ArraysBit ManipulationSliding Windows

You are given an array nums of non-negative integers and an integer k.

An array is called special if the bitwise OR of all of its elements is at least k.

Return the length of the shortest special non-empty subarray of nums, or return -1 if no special subarray exists.

For example:

nums = [1,2,3], k = 2. The subarray [3] has an OR value of 3. Hence, you should return 1.
nums = [2,1,8], k = 10. The subarray [2,1,8] has an OR value of 11. Hence, you should return 3.
nums = [1,2], k = 0. The subarray [1] has an OR value of 1. Hence, you should return 1.

Describe an efficient algorithm to solve this problem.

Shortest Subarray With OR at Least K II

Medium

Amazon

3 views

Topics:

ArraysBit ManipulationSliding Windows

You are given an array nums of non-negative integers and an integer k.

An array is called special if the bitwise OR of all of its elements is at least k.

Return the length of the shortest special non-empty subarray of nums, or return -1 if no special subarray exists.

For example:

nums = [1,2,3], k = 2. The subarray [3] has an OR value of 3. Hence, you should return 1.
nums = [2,1,8], k = 10. The subarray [2,1,8] has an OR value of 11. Hence, you should return 3.
nums = [1,2], k = 0. The subarray [1] has an OR value of 1. Hence, you should return 1.

Describe an efficient algorithm to solve this problem.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values within the input array and the target value 'K'? Can they be negative or zero?
If no subarray exists with an OR value of at least 'K', what should I return? Is there a specific value like -1 or null?
Is the input array guaranteed to be non-empty? What should I return if the input array is empty or null?
If multiple subarrays have the shortest length and an OR value of at least 'K', is it acceptable to return any one of them, or is there a preference (e.g., the one that starts earliest)?
Could you clarify whether the problem description implies a *contiguous* subarray, or if a non-contiguous subsequence would also be considered?

Brute Force Solution

Approach

The brute force approach means we're going to examine every possible chunk of numbers in our list. We will go through each chunk and see if it satisfies our condition: that the combined value of the numbers in the chunk is big enough.

Here's how the algorithm would work step-by-step:

Start by looking at the first number alone. Is it big enough?
Then, look at the first two numbers together. Is their combined value big enough?
Continue adding numbers one at a time to this chunk, checking each time if the combined value is big enough.
Once you've checked all possible chunks starting from the first number, move on to the second number.
Repeat the process: start with the second number alone, then the second and third, and so on.
Keep doing this until you've checked every possible chunk of numbers in the list.
While checking each chunk, remember the size of the smallest chunk that met the requirement.
After checking all the possibilities, give the size of that smallest chunk as the answer.

Code Implementation

def shortest_subarray_with_or_at_least_k_brute_force(numbers, k):
    shortest_length = float('inf')

    for start_index in range(len(numbers)): 
        current_or = 0
        for end_index in range(start_index, len(numbers)): 
            current_or |= numbers[end_index]

            # Check if the current subarray's OR value is at least k
            if current_or >= k:

                current_length = end_index - start_index + 1
                # Update shortest_length if current_length is shorter
                shortest_length = min(shortest_length, current_length)

    if shortest_length == float('inf'):
        return -1
    return shortest_length

Big(O) Analysis

Time Complexity

O(n²) – The described brute force approach iterates through all possible subarrays of the input array of size n. The outer loop iterates n times, once for each starting index of a subarray. The inner loop, for each starting index, iterates through all possible ending indices, resulting in a number of operations that decreases linearly from n-1 down to 0. Therefore, the total number of operations is proportional to the sum of the integers from 1 to n-1, which is n(n-1)/2. This simplifies to O(n²).

Space Complexity

O(1) – The provided brute force approach doesn't utilize any auxiliary data structures that scale with the input size N. It simply iterates through subarrays and calculates the OR value on the fly. No extra lists, hashmaps, or other data structures are created to store intermediate results; only a few variables to store the start and end indices of the subarray and the current OR value are used, therefore space complexity is constant, i.e., O(1).

Optimal Solution

Approach

The goal is to find the shortest possible chunk of numbers that, when combined using 'OR', reach a certain target value. Instead of checking every single chunk, we use a 'sliding window' to efficiently explore possible chunks, expanding and shrinking it as needed.

Here's how the algorithm would work step-by-step:

Start with a window covering no numbers initially.
Gradually expand the window to the right, including more numbers, and keep track of the 'OR' value of all the numbers within the window.
As you expand the window, check if the 'OR' value inside the window has reached or exceeded the target value.
If the target value is reached, try to shrink the window from the left, removing numbers from the beginning of the window, while still maintaining the 'OR' value at or above the target.
While shrinking, keep track of the smallest window size that still satisfies the target 'OR' value.
Continue expanding and shrinking the window as you move across all the numbers. The smallest window size you find during this process is the answer.

Code Implementation

def shortest_subarray_with_or_at_least_k(numbers, target_or):
    shortest_length = float('inf')
    current_or = 0
    window_start = 0

    for window_end in range(len(numbers)):
        current_or |= numbers[window_end]

        # Shrink the window from the left if the current OR is at least the target.
        while current_or >= target_or:

            current_window_length = window_end - window_start + 1

            # Update shortest length found so far
            shortest_length = min(shortest_length, current_window_length)

            # Remove the leftmost element from the window.
            current_or ^= numbers[window_start]
            window_start += 1

    if shortest_length == float('inf'):
        return -1
    else:
        return shortest_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses a sliding window approach, where we expand the window to the right and shrink it from the left. Each element of the input array of size n is considered at most twice: once when the right boundary of the window expands to include it, and once when the left boundary shrinks to exclude it. Therefore, the number of operations is proportional to the size of the input array, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm primarily uses a sliding window approach. It tracks the 'OR' value within the window and adjusts the window boundaries. No auxiliary data structures like lists or hashmaps are created to store intermediate results or visited elements. The memory used consists mainly of a few variables to store the current 'OR' value, window start and end indices, and the minimum window size found so far. Therefore, the space complexity is constant and independent of the input array size N.

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 (or appropriate error value) immediately as there's no subarray to process.
Array with a single element and K is greater than that element	Return -1 since a single element cannot satisfy the OR condition.
All elements in the array are 0 and K is greater than 0	Return -1 because the OR of any subarray will be 0, which is less than K.
K is 0	Return 1 if the array is not empty, as any single element subarray will have OR >= 0; special case if the array is empty, return -1.
Integer overflow when calculating OR	In languages like Java/C++, be cautious of integer overflow, but OR operation should not overflow unless the integers themselves are already overflowed.
Array contains large numbers such that the OR of all elements overflows	Handle potential overflow issues carefully; the problem description needs to constrain the max integer size, otherwise, a BigInteger solution is necessary.
No subarray exists that satisfies the condition	Return -1 if, after iterating through all possible subarrays, none meet the condition OR >= K.
Array contains negative numbers	The bitwise OR operation is well-defined for negative numbers; no special handling is required unless the problem statement explicitly forbids negative numbers.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values within the input array and the target value 'K'? Can they be negative or zero?
If no subarray exists with an OR value of at least 'K', what should I return? Is there a specific value like -1 or null?
Is the input array guaranteed to be non-empty? What should I return if the input array is empty or null?
If multiple subarrays have the shortest length and an OR value of at least 'K', is it acceptable to return any one of them, or is there a preference (e.g., the one that starts earliest)?
Could you clarify whether the problem description implies a *contiguous* subarray, or if a non-contiguous subsequence would also be considered?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the first number alone. Is it big enough?
Then, look at the first two numbers together. Is their combined value big enough?
Continue adding numbers one at a time to this chunk, checking each time if the combined value is big enough.
Once you've checked all possible chunks starting from the first number, move on to the second number.
Repeat the process: start with the second number alone, then the second and third, and so on.
Keep doing this until you've checked every possible chunk of numbers in the list.
While checking each chunk, remember the size of the smallest chunk that met the requirement.
After checking all the possibilities, give the size of that smallest chunk as the answer.

Code Implementation

def shortest_subarray_with_or_at_least_k_brute_force(numbers, k):
    shortest_length = float('inf')

    for start_index in range(len(numbers)): 
        current_or = 0
        for end_index in range(start_index, len(numbers)): 
            current_or |= numbers[end_index]

            # Check if the current subarray's OR value is at least k
            if current_or >= k:

                current_length = end_index - start_index + 1
                # Update shortest_length if current_length is shorter
                shortest_length = min(shortest_length, current_length)

    if shortest_length == float('inf'):
        return -1
    return shortest_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with a window covering no numbers initially.
Gradually expand the window to the right, including more numbers, and keep track of the 'OR' value of all the numbers within the window.
As you expand the window, check if the 'OR' value inside the window has reached or exceeded the target value.
If the target value is reached, try to shrink the window from the left, removing numbers from the beginning of the window, while still maintaining the 'OR' value at or above the target.
While shrinking, keep track of the smallest window size that still satisfies the target 'OR' value.
Continue expanding and shrinking the window as you move across all the numbers. The smallest window size you find during this process is the answer.

Code Implementation

def shortest_subarray_with_or_at_least_k(numbers, target_or):
    shortest_length = float('inf')
    current_or = 0
    window_start = 0

    for window_end in range(len(numbers)):
        current_or |= numbers[window_end]

        # Shrink the window from the left if the current OR is at least the target.
        while current_or >= target_or:

            current_window_length = window_end - window_start + 1

            # Update shortest length found so far
            shortest_length = min(shortest_length, current_window_length)

            # Remove the leftmost element from the window.
            current_or ^= numbers[window_start]
            window_start += 1

    if shortest_length == float('inf'):
        return -1
    else:
        return shortest_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 (or appropriate error value) immediately as there's no subarray to process.
Array with a single element and K is greater than that element	Return -1 since a single element cannot satisfy the OR condition.
All elements in the array are 0 and K is greater than 0	Return -1 because the OR of any subarray will be 0, which is less than K.
K is 0	Return 1 if the array is not empty, as any single element subarray will have OR >= 0; special case if the array is empty, return -1.
Integer overflow when calculating OR	In languages like Java/C++, be cautious of integer overflow, but OR operation should not overflow unless the integers themselves are already overflowed.
Array contains large numbers such that the OR of all elements overflows	Handle potential overflow issues carefully; the problem description needs to constrain the max integer size, otherwise, a BigInteger solution is necessary.
No subarray exists that satisfies the condition	Return -1 if, after iterating through all possible subarrays, none meet the condition OR >= K.
Array contains negative numbers	The bitwise OR operation is well-defined for negative numbers; no special handling is required unless the problem statement explicitly forbids negative numbers.