Longest Nice Subarray - Practice Coding Problems

Longest Nice Subarray - Problem

You are given an array nums consisting of positive integers.

We call a subarray of nums nice if the bitwise AND of every pair of elements that are in different positions in the subarray is equal to 0.

Return the length of the longest nice subarray.

A subarray is a contiguous part of an array.

Note: subarrays of length 1 are always considered nice.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: The longest nice subarray is [3,8,48] with length 3. Each pair has AND = 0: 3&8=0, 3&48=0, 8&48=0.

Example 2 — Single Element

$ Input: nums = [3,1,5,11,13]

› Output: 1

💡 Note: No pair of elements has AND = 0, so the longest nice subarray has length 1 (any single element).

Example 3 — All Elements Nice

$ Input: nums = [1,2,4]

› Output: 3

💡 Note: All elements have disjoint bits: 1&2=0, 1&4=0, 2&4=0. The entire array is nice with length 3.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,3,8,48,10] - find longest nice subarray

Process

Check subarrays where all pairs AND to 0

Output

Length 3 from subarray [3,8,48]

Key Takeaway

🎯 Key Insight: Elements in a nice subarray must have completely disjoint bit patterns

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is that a nice subarray requires all pairs to have bitwise AND = 0, meaning elements must have disjoint bits. The sliding window approach efficiently maintains an OR of the current window and shrinks when conflicts arise. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window - Two Pointers	O(n)	O(1)	Use sliding window to efficiently find longest nice subarray
Brute Force - Check All Subarrays	O(n³)	O(1)	Check every possible subarray to find the longest nice one

Sliding Window - Two Pointers — Algorithm Steps

Step 1: Use two pointers (left, right) and maintain OR of current window
Step 2: Expand right pointer, check if new element conflicts with window OR
Step 3: If conflict, shrink from left until no conflict, update max length

Visualization

Tap to expand

Step-by-Step Walkthrough

Expand Window

Move right pointer and check for conflicts

Resolve Conflicts

Shrink from left when AND ≠ 0

Update Maximum

Track longest valid window

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int left = 0;
    int maxLength = 1;
    int currentOr = 0;
    
    for (int right = 0; right < numsSize; right++) {
        // Check if adding nums[right] creates conflict
        while (left <= right && (currentOr & nums[right]) != 0) {
            currentOr ^= nums[left];  // Remove nums[left] from OR
            left++;
        }
        
        // Add nums[right] to current window
        currentOr |= nums[right];
        int currentLength = right - left + 1;
        if (currentLength > maxLength) {
            maxLength = currentLength;
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,2,3] format
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int val = atoi(token);
        if (val != 0 || token[0] == '0') {
            nums[numsSize++] = val;
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is visited at most twice (once by right pointer, once by left pointer)

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track pointers and OR value

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window - Two Pointers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler