Leetcode - Count Subarrays With Majority Element

문제

You are given an integer array nums and an integer target.

Return the number of subarrays of nums in which target is the majority element.

The majority element of a subarray is the element that appears strictly more than half of the times in that subarray.

• 정수 배열 nums와 target 정수가 주어진다.
• 배열의 부분배열중 target이 절반을 초과해 차지하는 배열의 갯수를 구하라

예시

[1, 2, 2, 3], 타겟: 2

• [2], [2], [2, 2], [1, 2, 2], [2, 2, 3] 이렇게 총 5개가 있다.

제한 ( 2번 Hard 문제 기준 )

• $1 <= nums.length <= 10^5$
• $1 <= nums[i] <= 10^9$
• $1 <= target <= 10^9$

풀이

기본 접근

• nums에서 target에 해당하는것만 절반보다 갯수가 크면 된다.
• 이것은 곧 target이 아닌것은 0, 인것은 1이라고 봐도 된다는 뜻!
• nums를 바이너리 배열로 만들어서 1의 갯수의 합이 크기의 절반보다 크면 된다는뜻이 된다.
• 근데 여기서 만약 같지 않은것을 -1로 만든다면?
• 부분배열의 합이 0보다 큰것을 전부 확인한다는 정말 간단한 공식으로 변경할수 있다!

부분배열로 접근

• 부분배열의 합은 보통 prefix sum으로 O(1) 시간복잡도로 구할수 있다.
• prefix 배열에 대해 부분배열의 합이 0보다 크다는것은 곧

$prefix[right + 1] - prefix[left] > 0$

• 근데 여기서 양변에 prefix[left]를 빼면?

$prefix[right + 1] > prefix[left]$

• 세상에 그냥 prefix sum에서 오른쪽에 있는값이 더 큰 쌍의 갯수를 구하는 문제가 되어 버린다.

그걸 어떻게 구할까

1. merge sort counting

• merge sort를 할때 우리는 왼쪽 배열과 오른쪽 배열쌍을 계속 비교한다.
  merge sort 과정에서 왼쪽 구간과 오른쪽 구간이 각각 정렬되어 있으므로,
  two pointer로 cross pair를 한 번의 선형 스캔으로 셀 수 있다. 각 레벨마다 O(N), 전체 O(N log N)이 된다.

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        N = len(nums)

        count = [0] * (N + 1)

        for i in range(1, N + 1):
            if nums[i - 1] == target:
                count[i] += 1
            else:
                count[i] -= 1

            count[i] += count[i - 1]

        self.ans = 0

        def checker(start: int, mid: int, end: int):
            j = mid + 1

            for i in range(start, mid + 1):
                while j <= end and count[j] <= count[i]:
                    j += 1

                self.ans += end - j + 1

            temp = []
            l = start
            r = mid + 1

            while l <= mid and r <= end:
                if count[l] <= count[r]:
                    temp.append(count[l])
                    l += 1
                else:
                    temp.append(count[r])
                    r += 1

            while l <= mid:
                temp.append(count[l])
                l += 1

            while r <= end:
                temp.append(count[r])
                r += 1

            for i, v in enumerate(temp):
                count[start + i] = v

        def counter(start: int, end: int):
            if start >= end:
                return

            mid = (start + end) // 2
            counter(start, mid)
            counter(mid + 1, end)
            checker(start, mid, end)

        counter(0, N)

        return self.ans

prefix sum 자체를 이용하기, 증분 갱신법

• 지금까지 등장했던 prefix sum의 frequency를 관리하는 값과 자신에 해당하는 prefix sum보다 값이 작은 앞에 있는 prefix sum의 갯수를 구하는 두 변수가 필요하다.
• 만약 prefix sum의 값이 1 증가한다면, 증가하기 이전 값들이 작은 prefix에 포함되기에 그 갯수를 더한다.
• 만약 prefix sum의 값이 1 감소한다면, 감소한 뒤의 값에 대해 그 값보다는 더이상 클수 없기에 그 갯수를 뺀다.

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        N = len(nums)

        freq = defaultdict(int)
        freq[0] = 1

        value = 0
        ans = 0
        old = 0

        for i in range(1, N + 1):
            if nums[i - 1] == target:
                old += 1
                value += freq[old - 1]
            else:
                old -= 1
                value -= freq[old]

            ans += value
            freq[old] += 1

        return ans