Longest Subarray with Majority Greater than K

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

Find longest subarray where more than half of elements are greater than k.

Intuition

Find longest subarray where more than half of elements are greater than k.

Algorithm

1Encode: +1 if arr[i]>k, -1 otherwise. Find longest subarray with positive prefix sum.

Common Pitfalls

• Majority means > n/2 elements. +1/-1 encoding + prefix sum with first-occurrence tracking gives O(n).

Longest Subarray with Majority Greater than K.java

Java

// Approach: Replace elements: +1 if > k, -1 otherwise. Find longest subarray with positive sum using prefix sums.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    static int longestSubarray(int[] arr, int k) {
        int n = arr.length;
        int prefixSum = 0;
        int maxLen = 0;

        Map<Integer, Integer> hm = new HashMap<>();
        hm.put(0, -1);

        for (int i = 0; i < n; i++) {
            prefixSum += (arr[i] > k) ? 1 : -1;

            if (prefixSum > 0)
                maxLen = i + 1;

            if (hm.containsKey(prefixSum - 1))
                maxLen = Math.max(maxLen, i - hm.get(prefixSum - 1));

            if (!hm.containsKey(prefixSum))
                hm.put(prefixSum, i);
        }
        return maxLen;
    }
}

Was this solution helpful?