What is the best approach for Longest Strictly Increasing Subsequence With Non-Zero Bitwise AND?

The most efficient approach is bit enumeration combined with the Longest Increasing Subsequence algorithm. Iterate through all 32 bit positions, keep numbers containing the chosen bit, and compute LIS using binary search. This guarantees every adjacent pair has a non‑zero AND and runs in O(32 * n log n) time with O(n) space.

Is Longest Strictly Increasing Subsequence With Non-Zero Bitwise AND asked at Google/Amazon/Meta?

Problems combining LIS with bit manipulation patterns commonly appear in interviews at companies like Google, Amazon, and Meta. Variants that mix subsequence DP with bit constraints are especially common in medium to hard algorithm rounds.

What data structure is used in Longest Strictly Increasing Subsequence With Non-Zero Bitwise AND?

The optimized solution uses an array or list called the tails array for the LIS patience sorting technique along with binary search. Bit masking operations are used to filter numbers sharing a particular bit.

What is the time complexity of Longest Strictly Increasing Subsequence With Non-Zero Bitwise AND?

A straightforward dynamic programming solution runs in O(n^2) time by checking every pair (j, i) for increasing order and non-zero AND. The optimized solution enumerates 32 bits and runs LIS with binary search, resulting in O(32 * n log n) time and O(n) space.

Description Hints 4 Solution Video 27:01

3825. Longest Strictly Increasing Subsequence With Non-Zero Bitwise AND

Q: Is Longest Strictly Increasing Subsequence With Non-Zero Bitwise AND easy or hard?

The problem is rated Medium because it requires combining two ideas: bit manipulation and the optimized LIS algorithm. Recognizing the shared-bit property and reducing the problem to multiple LIS computations is the main challenge.

Q: Longest Strictly Increasing Subsequence With Non-Zero Bitwise AND Python/Java solution

Implement bit enumeration and run a binary-search-based LIS for each bit. Python typically uses the bisect module for the LIS step, while Java uses Collections.binarySearch or a custom binary search on the tails array.

Q: How to solve Longest Strictly Increasing Subsequence With Non-Zero Bitwise AND in O(n log n)?

Filter numbers by a specific bit and compute the Longest Increasing Subsequence using the patience sorting method with binary search. Repeat this for each bit position from 0 to 31 and take the maximum LIS length found. Each LIS computation costs O(n log n), leading to O(32 * n log n) overall.

Medium49.5% acceptance

You are given an integer array nums.

Return the length of the longest strictly increasing subsequence in nums whose bitwise AND is non-zero. If no such subsequence exists, return 0.

Example 1:

Input: nums = [5,4,7]

Output: 2

Explanation:

One longest strictly increasing subsequence is [5, 7]. The bitwise AND is 5 AND 7 = 5, which is non-zero.

Example 2:

Input: nums = [2,3,6]

Output: 3

Explanation:

The longest strictly increasing subsequence is [2, 3, 6]. The bitwise AND is 2 AND 3 AND 6 = 2, which is non-zero.

Example 3:

Input: nums = [0,1]

Output: 1

Explanation:

One longest strictly increasing subsequence is [1]. The bitwise AND is 1, which is non-zero.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹

Topics

Hints open one at a time

Hint 1

Solve bit-by-bit for each b in 0..30.

Hint 2

Filter: take elements with bit b set, preserving order.

Hint 3

On that filtered sequence compute the longest increasing subsequence (LIS).

Hint 4

Return the maximum LIS over all bits; if no candidates return 0.

27:01

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def longestSubsequence(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[5,4,7]

Input

[2,3,6]

Input

[0,1]

Your code is saved on this device.Solution