Longest Strictly Increasing Subsequence With Non-Zero Bitwise AND - Solution & Explanation

Problem Overview: Given an integer array, find the length of the longest strictly increasing subsequence where the bitwise AND between every adjacent pair in the subsequence is non‑zero. The subsequence must preserve order and increase in value while sharing at least one common bit.

Approach 1: Dynamic Programming Enumeration (O(n^2) time, O(n) space)

Start with the classic array LIS idea. Let dp[i] represent the longest valid subsequence ending at index i. For each i, iterate all previous indices j < i. If nums[j] < nums[i] and (nums[j] & nums[i]) != 0, extend the subsequence: dp[i] = max(dp[i], dp[j] + 1). Track the maximum across all indices. The logic is straightforward and clearly enforces both constraints: increasing order and non‑zero AND. The downside is the quadratic scan across pairs, which becomes slow for large arrays.

Approach 2: Bit Enumeration + Longest Increasing Subsequence (O(32 * n log n) time, O(n) space)

The key observation: if every element in the subsequence shares at least one common bit position, then the AND between adjacent elements will always be non‑zero. Enumerate each bit from 0 to 31. For a chosen bit, filter numbers whose binary representation contains that bit. Those numbers automatically satisfy the AND constraint with each other.

Now the problem reduces to finding the Longest Increasing Subsequence among this filtered list. Use the classic patience sorting technique with binary search. Maintain a tails array where tails[k] stores the smallest ending value for an increasing subsequence of length k+1. For each number, use binary search to find its position and update the structure. This computes LIS in O(n log n) time per bit. Since there are at most 32 bits, the total complexity is O(32 * n log n).

This approach works because any valid subsequence must share at least one bit across its elements. By enumerating each bit and computing LIS independently, you guarantee that every candidate subsequence satisfies the bitwise constraint. Bit enumeration combined with LIS transforms a constraint-heavy problem into a standard subsequence optimization using bit manipulation.

Recommended for interviews: The bit enumeration + LIS approach. Starting with the quadratic DP shows you understand subsequence transitions and the AND constraint. Recognizing the shared-bit property and converting it to multiple LIS computations demonstrates strong pattern recognition and optimization skills, which is what interviewers expect for a medium-level problem.