Leetcode 2401: Longest Nice Subarray

Input: You are given an array of positive integers `nums`.

Example: nums = [2, 4, 8, 16]

Constraints:

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9

Output: Return the length of the longest nice subarray.

Example: Output: 3

Constraints:

Goal: The goal is to find the longest subarray where the bitwise AND between every pair of different elements is 0.

Steps:

• 1. Initialize variables for storing the result and the current bitwise AND of the subarray.

• 2. Iterate through the array while maintaining a sliding window to find the longest nice subarray.

• 3. For each element, check if the bitwise AND with the current subarray is 0. If it’s not 0, adjust the window to satisfy the condition.

• 4. Update the result with the length of the longest nice subarray found during the iteration.

Goal: The problem constraints ensure that the input array is within a reasonable range for efficient computation using a sliding window approach.

Steps:

• Array length can go up to 100,000, so the solution must be efficient, ideally O(n).

• Element values can be as large as 10^9, so bitwise operations must be handled efficiently.

Assumptions:

• The input array is valid and contains only positive integers.

• The array may contain large numbers, so bitwise operations must be optimized.

• Input: nums = [1,3,8,48,10]

• Explanation: The longest nice subarray is [3, 8, 48]. This subarray satisfies the conditions because the bitwise AND of every pair of different elements in the subarray is 0.

• Input: nums = [1, 2, 3, 4]

• Explanation: The longest nice subarray is [1], as any larger subarray will violate the condition that the bitwise AND of every pair of different elements is 0.

Approach: To solve this problem, we use a sliding window approach where we maintain a window of elements that form a nice subarray. We adjust the window size when the AND condition is violated.

Observations:

• The bitwise AND operation can be expensive, but the problem can be tackled efficiently using the sliding window technique.

• We need to find the longest subarray where the bitwise AND between every pair of distinct elements is 0.

Steps:

• 1. Initialize two pointers to represent the current subarray window.

• 2. Use a variable to store the bitwise AND of the current subarray.

• 3. Iterate through the array, extending the window to include new elements.

• 4. If the bitwise AND condition is violated, shrink the window from the left until the condition is satisfied again.

• 5. Update the result with the length of the largest valid subarray found.

Empty Inputs:

• This problem does not have an empty input case as the length of the array is guaranteed to be at least 1.

Large Inputs:

• For large arrays, the sliding window approach ensures that the solution runs efficiently with a time complexity of O(n).

Special Values:

• If the array contains only one element, the result is always 1, as any single element forms a valid nice subarray.

Constraints:

• The sliding window approach allows for efficient handling of large inputs within the given constraints.

int longestNiceSubarray(vector<int>& nums) {
    int res = 1, AND = 0, n = nums.size(), j = 0;
    for(int i = 0; i < n; i++) {
        while(((AND & nums[i]) > 0)) {
            AND ^= nums[j++];
        }
        AND |= nums[i];
        res = max(res, i - j + 1);
    }
    return res;
}

1 : Function Declaration

int longestNiceSubarray(vector<int>& nums) {

This is the function signature where we define the function `longestNiceSubarray` which takes a reference to a vector of integers `nums`.

2 : Variable Initialization

    int res = 1, AND = 0, n = nums.size(), j = 0;

We initialize variables: `res` to store the result (set to 1 initially), `AND` to perform bitwise operations (initialized to 0), `n` for the size of the array, and `j` as a pointer for the sliding window.

3 : Loop Start

    for(int i = 0; i < n; i++) {

A for-loop to iterate over the elements of the array `nums` from the first to the last element.

4 : While Loop for Sliding Window

        while(((AND & nums[i]) > 0)) {

This while-loop is used to shrink the sliding window by incrementing `j` while the bitwise AND of the current `AND` and `nums[i]` is greater than 0.

5 : Update AND

            AND ^= nums[j++];

Perform a bitwise XOR operation on `AND` with `nums[j]`, then increment `j` to shrink the window.

6 : Update AND

        AND |= nums[i];

Update the `AND` variable by performing a bitwise OR operation with `nums[i]`.

7 : Update Result

        res = max(res, i - j + 1);

Update the result `res` to the maximum of its current value and the current length of the sliding window (`i - j + 1`).

8 : Return Statement

    return res;

Return the final result `res` which is the length of the longest nice subarray.

Best Case: O(n), where n is the length of the array, since the sliding window approach only requires a single pass through the array.

Average Case: O(n), the sliding window approach maintains efficiency by ensuring each element is processed at most twice.

Worst Case: O(n), as in the worst case, the window may shrink for each element in the array.

Description: The solution runs in linear time, which is optimal for the problem's constraints.

Best Case: O(1), space usage remains constant even for the smallest inputs.

Worst Case: O(1), as the solution only requires a constant amount of extra space beyond the input array.

Description: The space complexity is constant, as we only need a few variables to track the window and the result.

Leetcode 2401: Longest Nice Subarray

Explore →