Longest Subarray With Maximum Bitwise AND

Longest Subarray With Maximum Bitwise AND - Problem

You are given an integer array nums of size n.

Consider a non-empty subarray from nums that has the maximum possible bitwise AND.

In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: The maximum bitwise AND is 3 (from element 3). The longest subarray with AND equal to 3 is [3,3] with length 2.

Example 2 — Single Element

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

› Output: 1

💡 Note: Maximum element is 4. The longest subarray with maximum AND is [4] with length 1.

Example 3 — All Same Elements

$ Input: nums = [5,5,5,5]

› Output: 4

💡 Note: All elements are 5, so the entire array has AND value 5. Length is 4.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with various integer elements

Key Insight

Maximum AND equals maximum element value

Find Sequence

Locate longest consecutive sequence of max element

Key Takeaway

🎯 Key Insight: Maximum bitwise AND of any subarray equals the maximum array element - find longest consecutive sequence of max element

Asked in

🍎 Apple 12 M Microsoft 8

The key insight is that the maximum possible bitwise AND of any subarray equals the maximum element in the array, since AND operations can only decrease or maintain bit values. The optimal approach finds the maximum element in O(n) time, then scans for the longest consecutive sequence of that element. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subarrays	O(n³)	O(1)	Generate all subarrays, compute their AND, find maximum AND and longest subarray with that AND
Optimized - Two Pass Solution	O(n)	O(1)	First pass finds maximum element, second pass finds longest consecutive sequence of maximum elements

Brute Force - Check All Subarrays — Algorithm Steps

Step 1: Generate all possible subarrays using nested loops
Step 2: For each subarray, calculate bitwise AND of all elements
Step 3: Track maximum AND value and longest length achieving it

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Create all possible contiguous subarrays

Calculate AND

Compute bitwise AND for each subarray

Track Maximum

Find maximum AND value and longest length

Code -

solution.c — C

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

int solution(int* nums, int numsSize) {
    int maxAnd = 0;
    int maxLength = 0;
    
    // Check all possible subarrays
    for (int i = 0; i < numsSize; i++) {
        for (int j = i; j < numsSize; j++) {
            // Calculate AND of subarray nums[i:j+1]
            int currentAnd = nums[i];
            for (int k = i + 1; k <= j; k++) {
                currentAnd &= nums[k];
            }
            
            // Update maximum AND and length
            if (currentAnd > maxAnd) {
                maxAnd = currentAnd;
                maxLength = j - i + 1;
            } else if (currentAnd == maxAnd) {
                if (j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                }
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops: O(n²) subarrays × O(n) AND computation per subarray

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables to track maximum AND and length

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

856 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

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler