What is the time complexity of Longest Nice Subarray?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Longest Nice Subarray?

This problem uses Array, Bit Manipulation, Sliding Window. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Longest Nice Subarray?

Insight 1: The bitwise AND condition implies that no two numbers in a 'nice' subarray can have the same bit set to 1. Insight 2: Using a sliding window technique is efficient to maintain and check subarrays for the 'nice' property as we iterate through the input array.

Which companies ask LeetCode 2401. Longest Nice Subarray in interviews?

This problem is frequently asked at Paytm.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Longest Nice Subarray - LeetCode 2401 Solution

Longest Nice Subarray - Complete Solution Guide

Longest Nice Subarray is LeetCode problem 2401, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 that subarrays of length 1 are always considered nice. Example 1: Input: nums = [1,3,8,48,10] Output: 3 Explanation: The longest nice subarray is [3,8,48]. This subarray satisfies the conditions: - 3

Detailed Explanation

The problem asks us to find the longest subarray within a given array of positive integers such that the bitwise AND of any two distinct elements within that subarray is equal to 0. A subarray is a contiguous sequence of elements within the original array. A 'nice' subarray is one that satisfies the aforementioned bitwise AND condition. A subarray of length 1 is always considered 'nice'.

Solution Approach

The solution utilizes a sliding window approach. We maintain a window defined by 'left' and 'right' pointers, representing the start and end of the current subarray. We also maintain a variable 'current_or' which holds the bitwise OR of all elements within the current window. As we iterate through the array with the 'right' pointer, we check if adding the current element at 'nums[right]' to the window violates the 'nice' property. If it does (i.e., '(current_or & nums[right]) != 0'), we shrink the window from the left by removing elements until the 'nice' property is restored. We then add 'nums[right]' to the window (by updating 'current_or') and update the maximum length of a 'nice' subarray encountered so far.

Step-by-Step Algorithm

Step 1: Initialize 'left' to 0, 'current_or' to 0, and 'max_length' to 0. These variables will store the left boundary of the window, the bitwise OR of elements in the window, and the maximum length of a 'nice' subarray, respectively.
Step 2: Iterate through the input array 'nums' using the 'right' pointer, starting from 0.
Step 3: While the bitwise AND of 'current_or' and 'nums[right]' is not 0, it means that adding 'nums[right]' to the current subarray would violate the 'nice' property.
Step 4: If the 'nice' property is violated, shrink the window from the left. Remove the leftmost element 'nums[left]' from the current subarray by XORing it with 'current_or' (current_or ^= nums[left]). Increment the 'left' pointer.
Step 5: After shrinking the window as necessary, add the current element 'nums[right]' to the current subarray by performing a bitwise OR: 'current_or |= nums[right]'.
Step 6: Update 'max_length' to the maximum of its current value and the length of the current subarray ('right - left + 1').
Step 7: After iterating through all elements in 'nums', return 'max_length'.

Key Insights

Insight 1: The bitwise AND condition implies that no two numbers in a 'nice' subarray can have the same bit set to 1.
Insight 2: Using a sliding window technique is efficient to maintain and check subarrays for the 'nice' property as we iterate through the input array.
Insight 3: The bitwise OR operation can be used to keep track of the bits that are set to 1 within the current subarray's elements. We can efficiently determine if adding a new element would violate the 'nice' property by checking if the bitwise AND of the current OR value and the new element is 0.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Bit Manipulation, Sliding Window.

Companies

Asked at: Paytm.

Longest Nice Subarray | LeetCode 2401

Medium

Array Bit Manipulation Sliding Window

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int longestNiceSubarray(int[] nums) {
        int left = 0;
        int current_or = 0;
        int max_length = 0;
        for (int right = 0; right < nums.length; right++) {
            while ((current_or & nums[right]) != 0) {
                current_or ^= nums[left];
                left += 1;
            }

            current_or |= nums[right];
            max_length = Math.max(max_length, right - left + 1);
        }
        return max_length;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2401: Longest Nice Subarray - Detailed explanation and solution approaches.

Topics

Array Bit Manipulation Sliding Window

Companies

Paytm

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:2401

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Initialize 'left' to 0, 'current_or' to 0, and 'max_length' to 0. These variables will store the left boundary of the window, the bitwise OR of elements in the window, and the maximum length of a 'nice' subarray, respectively.
2
Step 2: Iterate through the input array 'nums' using the 'right' pointer, starting from 0.
3
Step 3: While the bitwise AND of 'current_or' and 'nums[right]' is not 0, it means that adding 'nums[right]' to the current subarray would violate the 'nice' property.
4
Step 4: If the 'nice' property is violated, shrink the window from the left. Remove the leftmost element 'nums[left]' from the current subarray by XORing it with 'current_or' (current_or ^= nums[left]). Increment the 'left' pointer.
5
Step 5: After shrinking the window as necessary, add the current element 'nums[right]' to the current subarray by performing a bitwise OR: 'current_or |= nums[right]'.
6
Step 6: Update 'max_length' to the maximum of its current value and the length of the current subarray ('right - left + 1').
7
Step 7: After iterating through all elements in 'nums', return 'max_length'.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is linear because each element in the input array is visited at most twice (once by the 'right' pointer and at most once by the 'left' pointer). The space complexity is constant because the amount of memory used by the algorithm does not scale with the size of the input.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Iterate through all possible subarrays and check if each subarray is 'nice'.

Time: O(n^3), where n is the length of the input array. O(n^2) for generating all subarrays and O(n) for checking if a subarray is 'nice'.Space: O(1).

Trade-offs: The brute force approach is simple to understand but has a high time complexity and would likely result in a Time Limit Exceeded (TLE) error for larger inputs. The sliding window approach is more efficient.

✨

Key Insights

1Insight 1: The bitwise AND condition implies that no two numbers in a 'nice' subarray can have the same bit set to 1.
2Insight 2: Using a sliding window technique is efficient to maintain and check subarrays for the 'nice' property as we iterate through the input array.
3Insight 3: The bitwise OR operation can be used to keep track of the bits that are set to 1 within the current subarray's elements. We can efficiently determine if adding a new element would violate the 'nice' property by checking if the bitwise AND of the current OR value and the new element is 0.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Sliding Window

A moving "window" over data to process subsets efficiently.

Edge Cases

Edge case 1: Empty array. The given constraints specify that nums.length >= 1, so we don't need to explicitly handle the case of an empty array. The algorithm will correctly return 0 if an empty array was somehow passed in.
Edge case 2: Array with only one element. The algorithm correctly handles this case because a subarray of length 1 is always considered nice. The result will be 1.
Edge case 3: Array where all elements have mutually exclusive bits (e.g., powers of 2). The entire array will be a 'nice' subarray, and the algorithm will correctly return the length of the array.
Edge case 4: Array where no two elements are 'nice' together (e.g., all elements are odd). The algorithm will return 1 because only subarrays of length 1 are possible.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not shrinking the window correctly when the 'nice' property is violated. It's crucial to remove elements from the left until the bitwise AND condition is met before adding the new element to the window.

✗Common mistake 2: Forgetting to update the 'max_length' after adding an element to the window. The length of the current subarray needs to be compared with the current 'max_length' to keep track of the longest 'nice' subarray encountered so far.

✗Common mistake 3: Using the bitwise AND operator '&' incorrectly when trying to build the current OR value. The bitwise OR operator '|' is what is needed to add bits to the 'current_or' variable.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Network routing. Determining if different network segments can be combined into a single subnet without causing address collisions (where the AND of two addresses isn't 0).

🏦Real-world scenario 2: Database query optimization. When designing bitmasks for filtering database records, ensuring the selected filters are mutually exclusive to avoid unexpected results or performance bottlenecks.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 1, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Longest Nice Subarray"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether bit manipulation techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?