1157. Online Majority Element In Subarray #

Problem #

Implementing the class MajorityChecker, which has the following API:

• MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr;
• int query(int left, int right, int threshold) has arguments such that:
  • 0 <= left <= right < arr.length representing a subarray of arr;
  • 2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray

Each query(...) returns the element in arr[left], arr[left+1], ..., arr[right] that occurs at least threshold times, or -1 if no such element exists.

Example:

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2

Constraints:

• 1 <= arr.length <= 20000
• 1 <= arr[i] <= 20000
• For each query, 0 <= left <= right < len(arr)
• For each query, 2 * threshold > right - left + 1
• The number of queries is at most 10000

Problem Summary #

Implement a class MajorityChecker, which should have the following APIs:

• MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr.
• int query(int left, int right, int threshold) has the following parameters:
• 0 <= left <= right < arr.length represents a subarray of the array arr.
• 2 * threshold > right - left + 1, that is, the threshold threshold is always greater than half the length of the subsequence.

Each query query(…) returns the element that appears at least threshold times in arr[left], arr[left+1], …, arr[right]. If no such element exists, return -1.

Tips:

• 1 <= arr.length <= 20000
• 1 <= arr[i] <= 20000
• For each query, 0 <= left <= right < len(arr)
• For each query, 2 * threshold > right - left + 1
• The number of queries is at most 10000

Solution Approach #

• Design a data structure that can determine whether a majority element exists in any interval. The definition of a majority element is: the number appears more than half the length of the interval. If a majority element exists, it must be unique. If no majority element can be found in the given interval, output -1.

• This problem has a very conspicuous “hint”: 2 * threshold > right - left + 1. This condition is exactly the prerequisite of the Boyer-Moore voting algorithm. For the idea of Boyer-Moore voting, see problem 169. This problem also requires interval queries, so use the segment tree data structure to implement it. After analysis, the solution to this problem can be determined as Boyer-Moore voting + segment tree.

• The idea of Boyer-Moore voting is to use two variables, candidate and count, to record the element waiting to be voted out and the accumulated number of rounds in which the candidate has not been voted out. If the accumulated number of rounds in which the candidate has not been voted out is larger, then the possibility that it eventually becomes the majority element is greater. Scan the entire array from left to right. First take the first element as candidate. If the same element is encountered, accumulate the number of rounds. If a different element is encountered, vote out candidate together with the different element. When the number of rounds becomes 0, choose the next element as candidate. Scanning from left to right can find the majority element. So how can this be combined with a segment tree?

• A segment tree splits a large interval into many small intervals, so consider the following question. If Boyer-Moore voting is used in each small interval, and finally all small intervals are merged and Boyer-Moore voting is used once more, is the result the same as using Boyer-Moore voting once on the whole interval? The answer is yes. You can think of it this way: the majority element will always be selected in some interval, while Boyer-Moore voting in other intervals plays a “neutralizing” role, that is, elements are eliminated in pairs. Once this question is understood, it shows that Boyer-Moore voting has an additive property. Since it satisfies additivity, it can be combined with a segment tree, because each segment of a segment tree is added together and finally merged into a large interval.

• For example, arr = [1,1,2,2,1,1]. First construct the segment tree, as shown in the left figure below.

  

  Now each segment tree node no longer stores only one int number, but stores candidate and count. The candidate and count of each node respectively represent the Boyer-Moore voting result within that interval. During initialization, first fill every leaf: candidate is itself and count = 1. That is, the green nodes in the right figure. Then during pushUp, perform Boyer-Moore voting:

    mc.merge = func(i, j segmentItem) segmentItem {
            if i.candidate == j.candidate {
                return segmentItem{candidate: i.candidate, count: i.count + j.count}
            }
            if i.count > j.count {
                return segmentItem{candidate: i.candidate, count: i.count - j.count}
            }
            return segmentItem{candidate: j.candidate, count: j.count - i.count}
        }
  

  Until the candidate and count of the root node are both filled. Note that the count here is not the total number of occurrences of the element, but the number of rounds in Boyer-Moore voting in which it has persisted without being voted out. After the segment tree is built, you can start querying the majority element in any interval; candidate is the majority element. Next, you still need to determine whether the majority element satisfies the threshold condition.

• Use a dictionary to record the indices where each element appears in the array. For example, in the above example, use map to record the indices: count = map[1:[0 1 4 5] 2:[2 3]]. Since the indices are increasing during the recording process, the condition for binary search is satisfied. Using this dictionary, you can find the number of times a specified element appears in any interval. For example, here we need to find the number of times 1 appears in the interval [0,5]. Then use 2 binary searches to find lowerBound and upperBound respectively. In the interval [lowerBound, upperBound), all elements are 1, so the interval length is the number of repeated occurrences of that element. Compare it with threshold; if it is ≥ threshold, it means the answer has been found, otherwise if it is not found, output -1.

Code #

package leetcode

import (
	"sort"
)

type segmentItem struct {
	candidate int
	count     int
}

// MajorityChecker define
type MajorityChecker struct {
	segmentTree []segmentItem
	data        []int
	merge       func(i, j segmentItem) segmentItem
	count       map[int][]int
}

// Constructor1157 define
func Constructor1157(arr []int) MajorityChecker {
	data, tree, mc, count := make([]int, len(arr)), make([]segmentItem, 4*len(arr)), MajorityChecker{}, make(map[int][]int)
	// This merge function is the Boyer-Moore voting algorithm
	mc.merge = func(i, j segmentItem) segmentItem {
		if i.candidate == j.candidate {
			return segmentItem{candidate: i.candidate, count: i.count + j.count}
		}
		if i.count > j.count {
			return segmentItem{candidate: i.candidate, count: i.count - j.count}
		}
		return segmentItem{candidate: j.candidate, count: j.count - i.count}
	}
	for i := 0; i < len(arr); i++ {
		data[i] = arr[i]
	}
	for i := 0; i < len(arr); i++ {
		if _, ok := count[arr[i]]; !ok {
			count[arr[i]] = []int{}
		}
		count[arr[i]] = append(count[arr[i]], i)
	}
	mc.data, mc.segmentTree, mc.count = data, tree, count
	if len(arr) > 0 {
		mc.buildSegmentTree(0, 0, len(arr)-1)
	}
	return mc
}

func (mc *MajorityChecker) buildSegmentTree(treeIndex, left, right int) {
	if left == right {
		mc.segmentTree[treeIndex] = segmentItem{candidate: mc.data[left], count: 1}
		return
	}
	leftTreeIndex, rightTreeIndex := mc.leftChild(treeIndex), mc.rightChild(treeIndex)
	midTreeIndex := left + (right-left)>>1
	mc.buildSegmentTree(leftTreeIndex, left, midTreeIndex)
	mc.buildSegmentTree(rightTreeIndex, midTreeIndex+1, right)
	mc.segmentTree[treeIndex] = mc.merge(mc.segmentTree[leftTreeIndex], mc.segmentTree[rightTreeIndex])
}

func (mc *MajorityChecker) leftChild(index int) int {
	return 2*index + 1
}

func (mc *MajorityChecker) rightChild(index int) int {
	return 2*index + 2
}

// Query define
func (mc *MajorityChecker) query(left, right int) segmentItem {
	if len(mc.data) > 0 {
		return mc.queryInTree(0, 0, len(mc.data)-1, left, right)
	}
	return segmentItem{candidate: -1, count: -1}
}

func (mc *MajorityChecker) queryInTree(treeIndex, left, right, queryLeft, queryRight int) segmentItem {
	midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, mc.leftChild(treeIndex), mc.rightChild(treeIndex)
	if queryLeft <= left && queryRight >= right { // segment completely inside range
		return mc.segmentTree[treeIndex]
	}
	if queryLeft > midTreeIndex {
		return mc.queryInTree(rightTreeIndex, midTreeIndex+1, right, queryLeft, queryRight)
	} else if queryRight <= midTreeIndex {
		return mc.queryInTree(leftTreeIndex, left, midTreeIndex, queryLeft, queryRight)
	}
	// merge query results
	return mc.merge(mc.queryInTree(leftTreeIndex, left, midTreeIndex, queryLeft, midTreeIndex),
		mc.queryInTree(rightTreeIndex, midTreeIndex+1, right, midTreeIndex+1, queryRight))
}

// Query define
func (mc *MajorityChecker) Query(left int, right int, threshold int) int {
	res := mc.query(left, right)
	if _, ok := mc.count[res.candidate]; !ok {
		return -1
	}
	start := sort.Search(len(mc.count[res.candidate]), func(i int) bool { return left <= mc.count[res.candidate][i] })
	end := sort.Search(len(mc.count[res.candidate]), func(i int) bool { return right < mc.count[res.candidate][i] }) - 1
	if (end - start + 1) >= threshold {
		return res.candidate
	}
	return -1
}

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * obj := Constructor(arr);
 * param_1 := obj.Query(left,right,threshold);
 */