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

This problem asks us to find the longest strictly increasing subsequence (LIS) in a given integer array nums, with the additional constraint that the bitwise AND of all elements in the subsequence must be non-zero.

leetcodemediumarraybinary-searchbit-manipulationenumeration

LeetCode Problem 3825

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Bit Manipulation, Enumeration

Solution

Problem Understanding

This problem asks us to find the longest strictly increasing subsequence (LIS) in a given integer array nums, with the additional constraint that the bitwise AND of all elements in the subsequence must be non-zero. In simpler terms, among all sequences you can extract from nums where each number is strictly larger than the previous, we want the one with maximum length whose elements, when combined using the bitwise AND operation, do not produce zero.

The input nums is an array of integers, where each integer ranges from 0 to $10^9$, and the length of the array is up to $10^5$. The output is a single integer representing the length of the longest valid subsequence, or 0 if no such subsequence exists.

Key points from the constraints are that the array can be very large and the numbers themselves can be big, so naive exhaustive enumeration of subsequences will be infeasible. Edge cases to be aware of include arrays containing zeroes (since any AND with 0 yields 0) and arrays where all numbers are identical or strictly decreasing.

Approaches

Brute Force

The brute-force approach would involve generating all strictly increasing subsequences, calculating the bitwise AND for each, and keeping track of the maximum length subsequence with a non-zero AND. This guarantees correctness but is extremely inefficient. For an array of length $n$, there are potentially $2^n$ subsequences. Even using dynamic programming to generate increasing subsequences, checking the AND for each subsequence still results in an exponential number of operations in the worst case.

Optimal Approach

The key insight is that the bitwise AND operation is monotonic with respect to bits: adding more numbers to a sequence can only turn more bits off, never on. Therefore, if the AND becomes zero at any point, appending additional numbers will never make it non-zero again. This allows us to combine dynamic programming for LIS with bitwise state tracking.

We maintain a dictionary (or map) dp where the keys are possible non-zero AND values, and the values are the length of the longest strictly increasing subsequence ending with that AND value. For each number in the array, we iterate over existing states in dp and compute the new AND values with the current number. We only keep the non-zero ANDs and update the length if it improves. Finally, the maximum value in dp is the answer.

This approach leverages the fact that the number of distinct AND values is limited by the number of bits in the integers (up to 30 bits for $10^9$), making it tractable.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(2^n) Generate all increasing subsequences and check AND
Optimal O(n * B) O(B) DP map tracks non-zero AND values; B is max number of bitwise states (~30)

Algorithm Walkthrough

  1. Initialize an empty dictionary dp to track non-zero AND values and their LIS lengths.
  2. Iterate through each number num in nums.
  3. For each existing AND value and_val in dp, compute new_and = and_val & num.
  4. If new_and is non-zero, update dp[new_and] = max(dp.get(new_and, 0), dp[and_val] + 1).
  5. Also consider starting a new subsequence with num itself: if num != 0, set dp[num] = max(dp.get(num, 0), 1).
  6. After processing all numbers, return the maximum length value in dp, or 0 if dp is empty.

Why it works: At every step, dp keeps track of the best subsequences for each possible non-zero AND. The key property is that bitwise AND is monotonic, so updating existing sequences by including the current number will only generate valid non-zero ANDs or discard zero results. This ensures we explore all feasible subsequences without exponential enumeration.

Python Solution

from typing import List

class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        dp = dict()  # maps non-zero AND value -> length of LIS ending with this AND
        for num in nums:
            updates = dict()
            if num != 0:
                updates[num] = max(updates.get(num, 0), 1)
            for and_val, length in dp.items():
                new_and = and_val & num
                if new_and != 0:
                    updates[new_and] = max(updates.get(new_and, 0), length + 1)
            for k, v in updates.items():
                dp[k] = max(dp.get(k, 0), v)
        return max(dp.values(), default=0)

In this implementation, we maintain a dictionary dp to record lengths of subsequences for each non-zero AND value. For each number, we calculate possible new AND values by combining it with existing sequences and update the dictionary. The final result is the maximum value among all lengths.

Go Solution

func longestSubsequence(nums []int) int {
    dp := make(map[int]int)
    for _, num := range nums {
        updates := make(map[int]int)
        if num != 0 {
            updates[num] = max(updates[num], 1)
        }
        for andVal, length := range dp {
            newAnd := andVal & num
            if newAnd != 0 {
                if updates[newAnd] < length+1 {
                    updates[newAnd] = length + 1
                }
            }
        }
        for k, v := range updates {
            if dp[k] < v {
                dp[k] = v
            }
        }
    }
    maxLen := 0
    for _, length := range dp {
        if length > maxLen {
            maxLen = length
        }
    }
    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Go requires explicit handling of maps and integer defaults. We create a temporary updates map to avoid modifying dp while iterating. The logic is otherwise identical to Python.

Worked Examples

Example 1: nums = [5,4,7]

Step dp state
num=5 {5: 1}
num=4 {5:1, 4:1} (4 & 5 = 4, update) → {5:1, 4:1}
num=7 combine with 5: 5&7=5 → length=2, combine with 4: 4&7=4 → length=2 → dp={5:2,4:2,7:1}

Max length = 2

Example 2: nums = [2,3,6]

Step dp state
num=2 {2:1}
num=3 2&3=2 → length=2, add 3 itself → {2:2,3:1}
num=6 2&6=2 → length=3, 3&6=2 → length=3, add 6 itself → {2:3,3:1,6:1}

Max length = 3

Example 3: nums = [0,1]

Step dp state
num=0 ignored
num=1 {1:1}

Max length = 1

Complexity Analysis

Measure Complexity Explanation
Time O(n * B) n is array length, B is max number of bits (~30) limiting distinct AND values
Space O(B) dp stores at most one entry per distinct non-zero AND value, bounded by number of bits

The reasoning is that although we iterate over dp for each number, the number of distinct non-zero AND values remains small due to the limited bit width of integers.

Test Cases

# provided examples
assert Solution().longestSubsequence([5,4,7]) == 2
assert Solution().longestSubsequence([2,3,6]) == 3
assert Solution().longestSubsequence([0,1]) == 1

# edge and stress cases
assert Solution().longestSubsequence([0,0,0]) == 0  # all zeros
assert Solution().longestSubsequence([1,1,1,1]) == 4  # repeated same number
assert Solution().longestSubsequence([1,2,4,8,16]) == 1  # powers of 2, AND always single number
assert Solution().longestSubsequence([7,7,7,7]) == 4  # same non-zero repeated
assert Solution().longestSubsequence([5,1,2,3,7]) == 3  # mixed values
Test Why
[5,4,7] normal case with subsequence of length 2
[2,3,6] longest sequence includes all numbers
[0,1] zero ignored, subsequence of length 1
[0,0,0] all zeros → return 0
[1,1