Longest Subarray with Majority Greater than K

JavaView on GFG

Time: O(n)

Space: O(n)

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?