Skip to main content
Talentd

Find Subarray With Bitwise OR Closest to K - Solution & Explanation

HardArrayBinary SearchBit ManipulationSegment Tree27 min readAsked at: Salesforce
Practice this problem

Problem Statement

You are given an array nums and an integer k. You need to find a subarray of nums such that the absolute difference between k and the bitwise OR of the subarray elements is as small as possible. In other words, select a subarray nums[l..r] such that |k - (nums[l] OR nums[l + 1] ... OR nums[r])| is minimum.

Return the minimum possible value of the absolute difference.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,2,4,5], k = 3

Output: 0

Explanation:

The subarray nums[0..1] has OR value 3, which gives the minimum absolute difference |3 - 3| = 0.

Example 2:

Input: nums = [1,3,1,3], k = 2

Output: 1

Explanation:

The subarray nums[1..1] has OR value 3, which gives the minimum absolute difference |3 - 2| = 1.

Example 3:

Input: nums = [1], k = 10

Output: 9

Explanation:

There is a single subarray with OR value 1, which gives the minimum absolute difference |10 - 1| = 9.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109

Approach Overview

Problem Overview: You are given an integer array and a value k. The goal is to choose a contiguous subarray whose bitwise OR is as close as possible to k. Instead of matching exactly, you minimize |OR - k| across all possible subarrays.

Approach 1: Brute Force with Prefix OR Computation (Time: O(n²), Space: O(1))

Enumerate every subarray starting at index i. Maintain a running OR value while extending the end index j. Because OR is monotonic when expanding a window (a | b | c never removes bits), you can reuse the previous OR instead of recomputing from scratch. For each extension, compute abs(current_or - k) and update the minimum difference. This approach is straightforward and demonstrates the key observation about OR accumulation, but it still checks O(n²) subarrays. It works for small inputs and is useful for validating optimized logic. The solution relies heavily on array traversal and bit manipulation behavior.

Approach 2: Two-Pointer Technique with Bit Tracking (Time: O(n * 32), Space: O(32))

Use a sliding window where the right pointer expands the subarray and the left pointer shrinks it. Since OR only increases when adding elements, you track how many times each bit (0–31) appears inside the window. When a number enters the window, increment counts for its set bits and recompute the current OR. When the window needs to shrink, decrement those counts; if a bit count becomes zero, remove that bit from the window OR. Each step updates the minimum difference with k. Because each element enters and leaves the window once and bit operations are limited to 32 positions, the total work becomes O(n * 32). This pattern combines sliding window logic with efficient bit accounting and is common in advanced bit manipulation problems.

Recommended for interviews: Start with the brute force explanation to show you understand how OR accumulates across subarrays. Then transition to the optimized sliding window with bit counts. Interviewers usually expect the optimized approach because it demonstrates deeper understanding of OR monotonicity, window maintenance, and efficient bit-level updates.

Approach 1: Approach 1: Brute Force with Prefix OR Computation

This approach involves using a nested loop to evaluate each possible subarray of the given array. We start at each index and calculate the OR value progressively by including more elements. A prefix OR allows us to efficiently compute the OR value for each subarray.

The function minAbsoluteDifference calculates the minimum absolute difference between k and the OR value of subarrays of nums. It iteratively evaluates each subarray, updating the minimum difference found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the size of the input array.
Space Complexity: O(1), as we're not using any additional space proportional to the input size.

Try this approach in the editor →

Approach 2: Approach 2: Two-Pointer Technique

This method uses a two-pointer technique to efficiently iterate through possible subarrays. We maintain a window with a left and right boundary, updating our OR value incrementally as we adjust the window to minimize the difference with k.

The two-pointer technique creates a dynamic window over the subarray to efficiently adjust the OR value. If this OR surpasses k, it adjusts the window to decrease its size from the left side.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), since we process each element at most twice.
Space Complexity: O(1), as our only additional storage is a few integer variables.

Try this approach in the editor →

Approach 3: Two Pointers + Bitwise Operations

According to the problem description, we need to calculate the result of the bitwise OR operation of elements from index l to r in the array nums, that is, nums[l] \lor nums[l + 1] \lor cdots \lor nums[r], where \lor represents the bitwise OR operation.

If we fix the right endpoint r, then the range of the left endpoint l is [0, r]. Each time we move the right endpoint r, the result of the bitwise OR operation will only increase. We use a variable s to record the current result of the bitwise OR operation. If s is greater than k, we move the left endpoint l to the right until s is less than or equal to k. During the process of moving the left endpoint l, we need to maintain an array cnt to record the number of 0s on each binary digit in the current interval. When cnt[h] = 0, it means that all elements in the current interval have a 0 on the h^{th} bit, and we can set the h^{th} bit of s to 0.

The time complexity is O(n times log M), and the space complexity is O(log M). Here, n and M respectively represent the length of the array nums and the maximum value in the array nums.

Similar Problems:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Hash Table + Enumeration

According to the problem description, we need to calculate the result of the bitwise OR operation of elements from index l to r in the array nums, that is, nums[l] \lor nums[l + 1] \lor cdots \lor nums[r]. Here, \lor represents the bitwise OR operation.

If we fix the right endpoint r, then the range of the left endpoint l is [0, r]. Since the sum of bitwise OR increases monotonically as l decreases, and the value of nums[i] does not exceed 10^9, the interval [0, r] can have at most 30 different values. Therefore, we can use a set to maintain all the values of nums[l] \lor nums[l + 1] \lor cdots \lor nums[r]. When we traverse from r to r+1, the values with r+1 as the right endpoint are the values obtained by performing the bitwise OR operation of each value in the set with nums[r + 1], plus nums[r + 1] itself. Therefore, we only need to enumerate each value in the set and perform the bitwise OR operation with nums[r], to get all the values for r as the right endpoint. Then, we take the absolute difference of each value with k, and the minimum of these differences is the answer.

The time complexity is O(n times log M), and the space complexity is O(log M). Here, n and M respectively represent the length of the array nums and the maximum value in the array nums.

Similar Problems:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Brute Force with Prefix OR Computation

Time Complexity: O(n^2), where n is the size of the input array.
Space Complexity: O(1), as we're not using any additional space proportional to the input size.

Approach 2: Two-Pointer Technique

Time Complexity: O(n), since we process each element at most twice.
Space Complexity: O(1), as our only additional storage is a few integer variables.

Two Pointers + Bitwise Operations—
Hash Table + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Incremental ORO(n²)O(1)Useful for understanding OR accumulation and validating logic on small inputs
Two-Pointer with Bit Frequency TrackingO(n * 32)O(32)Best general solution for large arrays; maintains window OR efficiently

Video Solution

leetcode 3171 Find Subarray With Bitwise OR Closest to K • Coder on A Farm • 252 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Find Subarray With Bitwise OR Closest to K easy or hard?
This problem is considered Hard because maintaining the bitwise OR while dynamically shrinking a window is non-trivial. The challenge comes from the fact that OR is not reversible, so you must track bit frequencies to correctly update the window value.
Find Subarray With Bitwise OR Closest to K Python/Java solution
Python, Java, C++, and other languages implement the same logic: maintain a sliding window and an array of 32 counters for bit frequencies. When adding or removing numbers from the window, update the counters and recompute the OR value. Track the minimum absolute difference from k during traversal.
How to solve Find Subarray With Bitwise OR Closest to K in O(n)?
Strict O(n) is difficult because maintaining a dynamic bitwise OR requires checking bit positions. The practical optimal solution runs in O(n * 32) using a sliding window and a frequency array for each bit. Each element updates the 32-bit counters when entering or leaving the window, allowing fast recomputation of the current OR.
What is the best approach for Find Subarray With Bitwise OR Closest to K?
The most efficient approach uses a sliding window (two-pointer technique) combined with bit frequency tracking. Each bit position (0–31) keeps a count of how many elements in the window contain that bit. This allows recomputing the window OR in constant time when expanding or shrinking the window. The overall complexity becomes O(n * 32).
Is Find Subarray With Bitwise OR Closest to K asked at Google/Amazon/Meta?
Problems involving subarray bitwise operations and sliding windows frequently appear in interviews at large tech companies. Variants of this problem test understanding of bit manipulation, window maintenance, and monotonic properties of OR operations, which are common themes in Google and Amazon coding interviews.
What data structure is used in Find Subarray With Bitwise OR Closest to K?
The optimized solution uses a sliding window with a small fixed-size array (size 32) to track bit frequencies. This acts like a lightweight counter structure for each bit position. Standard array traversal and bit manipulation operations are used to maintain the window OR efficiently.
What is the time complexity of Find Subarray With Bitwise OR Closest to K?
The brute force method checks every subarray and runs in O(n²) time. The optimized sliding window solution tracks bit counts and processes each element once when entering and leaving the window. Since each update touches at most 32 bits, the time complexity is O(n * 32) with O(32) extra space.

Ready to solve this problem?

Practice Find Subarray With Bitwise OR Closest to K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Sum of Values by Dividing Array