Katkat
Back

Elements Occurring More Than n/3 Times in a Sorted Array

ByteDanceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize frequency counting in a sorted array by leveraging binary search to achieve logarithmic time complexity, rather than a linear scan.

Problem Statement

Given a sorted array of integers nums, return a list of all elements that appear strictly more than n/3 times, where n is the length of the array.

Your solution should aim for a time complexity better than O(n) by utilizing the sorted property of the array.

Function Signature

def find_elements(nums: List[int]) -> List[int]:

Examples

Example 1: Input: nums = [1, 1, 2, 2, 3, 3, 3] Output: [3] Explanation: Length is 7, 7/3 = 2.33. The number 3 appears 3 times, which is > 2.33.

Example 2: Input: nums = [1, 2, 3] Output: [] Explanation: No element appears more than 1 time.

Constraints

  • n is the length of nums (1 <= n <= 10^5)
  • nums is sorted in non-decreasing order.

Edge Cases

  • An empty array or an array with very few elements.
  • An array where all elements are the same.
  • An array where no element satisfies the condition.

Hints

Hint 1

Since the array is sorted, all occurrences of a specific number are grouped together.

Hint 2

For any element at index `i`, you can find its first and last occurrence using binary search to determine its total frequency.

Hint 3

Because an element must appear more than `n/3` times, there can be at most two such elements; consider where these candidates could possibly start in the array.

Follow-up questions

  • How would you modify your approach if the array was not sorted?
  • Can you solve this using O(1) extra space if the array is unsorted (Boyer-Moore Voting Algorithm)?
  • What is the time complexity of your solution if you use binary search compared to a simple linear scan?