02. Longest Subarray with Majority Greater than K

✅ GFG solution to the Longest Subarray with Majority Greater than K problem: find maximum length subarray where count of elements > k exceeds count of elements ≤ k using prefix sum technique. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

You are given an array arr[] and an integer k. Your task is to find the length of the longest subarray in which the count of elements greater than k is more than the count of elements less than or equal to k.

A subarray is a contiguous sequence of elements within an array. The goal is to find the maximum possible length of such a subarray where elements > k have majority over elements ≤ k.

📘 Examples

Example 1

Input: arr[] = [1, 2, 3, 4, 1], k = 2
Output: 3
Explanation: The subarray [2, 3, 4] or [3, 4, 1] satisfy the given condition. 
In [2, 3, 4]: elements > 2 are [3, 4] (count = 2), elements ≤ 2 are [2] (count = 1).
Since 2 > 1, this subarray is valid with length 3.

Example 2

Input: arr[] = [6, 5, 3, 4], k = 2
Output: 4
Explanation: In the subarray [6, 5, 3, 4], there are 4 elements > 2 and 0 elements ≤ 2.
Since 4 > 0, the entire array satisfies the condition with length 4.

🔒 Constraints

$1 \le \text{arr.size()} \le 10^6$
$1 \le \text{arr}[i] \le 10^6$
$0 \le k \le 10^6$

✅ My Approach

The optimal approach uses the Prefix Sum technique with a Hash Map to efficiently track the balance between elements greater than k and elements less than or equal to k:

Prefix Sum + Hash Map

Transform Problem:
- Convert each element to +1 if arr[i] > k, otherwise -1 if arr[i] ≤ k.
- This transforms the problem to finding the longest subarray with positive sum.
Running Balance:
- Maintain a running sum where we add +1 for elements > k and -1 for elements ≤ k.
- A positive sum indicates more elements > k than elements ≤ k.
Hash Map for Optimization:
- Store the first occurrence of each sum value with its index.
- For current sum s, if we need sum > 0, we look for previous occurrence of s-1.
- This gives us the longest subarray ending at current position with positive balance.
Key Insights:
- If current sum > 0, the entire prefix from start has majority > k.
- If current sum ≤ 0, we look for a previous position where sum was current_sum - 1.
- The subarray between that position and current position will have sum = 1 (positive).
Edge Case Handling:
- Initialize map with sum 0 at index -1 to handle cases where entire prefix is valid.
- Only store first occurrence of each sum to maximize subarray length.

📝 Time and Auxiliary Space Complexity

Expected Time Complexity: O(n), where n is the size of the array. We make a single pass through the array, and each hash map operation takes O(1) average time.
Expected Auxiliary Space Complexity: O(n), where n is the size of the array. In the worst case, we might store all different sum values in the hash map, which can be at most n different values.

🧑‍💻 Code (C++)

class Solution {
public:
    int longestSubarray(vector<int>& arr, int k) {
        int n = arr.size(), ans = 0, sum = 0;
        unordered_map<int, int> mp;
        for (int i = 0; i < n; ++i) {
            sum += arr[i] <= k ? -1 : 1;
            if (sum > 0) ans = i + 1;
            else if (mp.count(sum - 1)) ans = max(ans, i - mp[sum - 1]);
            if (!mp.count(sum)) mp[sum] = i;
        }
        return ans;
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ Two Pointer Sliding Window

💡 Algorithm Steps:

Use running sum where ≤k adds -1 and >k adds +1 for balance calculation
Track count of elements ≤ k vs elements > k in current window
Expand window and update maximum when balance is positive
Use hash map to find previous positions with required balance

class Solution {
public:
    int longestSubarray(vector<int>& arr, int k) {
        int ans = 0, balance = 0;
        unordered_map<int, int> mp;
        mp[0] = -1;
        for (int i = 0; i < arr.size(); ++i) {
            balance += arr[i] <= k ? -1 : 1;
            if (balance > 0) ans = i + 1;
            else if (mp.count(balance - 1)) ans = max(ans, i - mp[balance - 1]);
            if (!mp.count(balance)) mp[balance] = i;
        }
        return ans;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n) - Single pass with hash map lookups
Auxiliary Space: 💾 O(n) - Hash map for balance tracking

✅ Why This Approach?

Clear balance tracking logic
Similar to original approach but different implementation
Good for understanding prefix sum concept

📊 3️⃣ Optimized Single Pass

💡 Algorithm Steps:

Maintain running sum where ≤k adds -1 and >k adds +1
Use only essential variables to minimize memory overhead
Track maximum length when sum becomes positive
Use map only when necessary for negative sum lookups

class Solution {
public:
    int longestSubarray(vector<int>& arr, int k) {
        unordered_map<int, int> m;
        int s = 0, res = 0;
        m[0] = -1;
        for (int i = 0; i < arr.size(); ++i) {
            s += arr[i] <= k ? -1 : 1;
            if (s > 0) res = i + 1;
            else if (m.find(s - 1) != m.end()) res = max(res, i - m[s - 1]);
            if (m.find(s) == m.end()) m[s] = i;
        }
        return res;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n) - Single traversal with hash map operations
Auxiliary Space: 💾 O(n) - Hash map for sum tracking

✅ Why This Approach?

Minimal variable usage for better performance
Clean implementation with essential logic only
Good balance of readability and efficiency

📊 4️⃣ Brute Force Approach

💡 Algorithm Steps:

Check all possible subarrays using nested loops
For each subarray, count elements > k and elements ≤ k
Update maximum length when count(>k) > count(≤k)
Return the maximum length found

class Solution {
public:
    int longestSubarray(vector<int>& arr, int k) {
        int n = arr.size(), maxLen = 0;
        for (int i = 0; i < n; i++) {
            int countGreater = 0, countLessEqual = 0;
            for (int j = i; j < n; j++) {
                if (arr[j] > k) countGreater++;
                else countLessEqual++;
                if (countGreater > countLessEqual) {
                    maxLen = max(maxLen, j - i + 1);
                }
            }
        }
        return maxLen;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n²) - Nested loops to check all subarrays
Auxiliary Space: 💾 O(1) - Only using constant extra space

✅ Why This Approach?

Simple to understand and implement
No additional data structures needed
Good for small input sizes or educational purposes

Note: This approach results in Time Limit Exceeded (TLE) for large inputs (fails ~1110 /1115 test cases due to time constraints).

🆚 🔍 Comparison of Approaches

🚀 Approach

⏱️ Time Complexity

💾 Space Complexity

✅ Pros

⚠️ Cons

🗺️ Hash Map

🟢 O(n)

🟡 O(n)

🎯 Handles all cases optimally

💾 Extra space for hash map

🔄 Alternative Hash Map

🟢 O(n)

🟡 O(n)

🚀 Different implementation

💾 Same space complexity

⚡ Optimized Single Pass

🟢 O(n)

🟡 O(n)

🧠 Minimal variable usage

💾 Still requires hash map

🐌 Brute Force

🔴 O(n²)

🟢 O(1)

💡 Simple, no extra space

⏰ Inefficient for large inputs

🏆 Best Choice Recommendation

🎯 Scenario

🎖️ Recommended Approach

🔥 Performance Rating

🏅 General optimal solution

🥇 Hash Map

★★★★★

💾 Alternative implementation

🥈 Alternative Hash Map

★★★★☆

🎓 Minimal code complexity

🏅 Optimized Single Pass

★★★★☆

📚 Educational/Small inputs

🏅 Brute Force

★★☆☆☆

☕ Code (Java)

class Solution {
    public int longestSubarray(int[] arr, int k) {
        int n = arr.length, ans = 0, sum = 0;
        Map<Integer, Integer> mp = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            sum += (arr[i] > k) ? 1 : -1;
            if (sum > 0) ans = i + 1;
            else if (mp.containsKey(sum - 1)) ans = Math.max(ans, i - mp.get(sum - 1));
            mp.putIfAbsent(sum, i);
        }
        return ans;
    }
}

🐍 Code (Python)

class Solution:
    def longestSubarray(self, arr, k):
        mp, ans, s = {0: -1}, 0, 0
        for i, x in enumerate(arr):
            s += -1 if x <= k else 1
            if s > 0: ans = i + 1
            elif s - 1 in mp: ans = max(ans, i - mp[s - 1])
            mp.setdefault(s, i)
        return ans

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count

Previous01. Balancing Consonants and Vowels Ratio Next03. 2D Difference Array

Last updated 5 months ago

hashtag🧩 Problem Description

hashtag📘 Examples

hashtagExample 1

hashtagExample 2

hashtag🔒 Constraints

hashtag✅ My Approach

hashtagPrefix Sum + Hash Map

hashtag📝 Time and Auxiliary Space Complexity

hashtag🧑‍💻 Code (C++)

hashtag📊 2️⃣ Two Pointer Sliding Window

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 3️⃣ Optimized Single Pass

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 4️⃣ Brute Force Approach

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag🆚 🔍 Comparison of Approaches

hashtag🏆 Best Choice Recommendation

hashtag☕ Code (Java)

hashtag🐍 Code (Python)

hashtag🧠 Contribution and Support

hashtag📍Visitor Count

🧩 Problem Description

📘 Examples

Example 1

Example 2

🔒 Constraints

✅ My Approach

Prefix Sum + Hash Map

📝 Time and Auxiliary Space Complexity

🧑‍💻 Code (C++)

📊 2️⃣ Two Pointer Sliding Window

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 3️⃣ Optimized Single Pass

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 4️⃣ Brute Force Approach

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

🆚 🔍 Comparison of Approaches

🏆 Best Choice Recommendation

☕ Code (Java)

🐍 Code (Python)

🧠 Contribution and Support

📍Visitor Count