I was asked the following in an interview:
Given a sorted array with n numbers (where n is a multiple of 4), return whether any number appears more than n/4 times.
My initial thought was to iterate over the array and keep a counter:
limit = len(nums) // 4
counter = 1
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
counter += 1
if counter > limit:
return True
else:
counter = 1
return False
However the interviewer asked if I could do better. Sorted array, better than linear complexity, I immediately thought “binary search”… I explored this path but was clueless.
After a few minutes, he gave a hint: “if any i exists where nums[i] == nums[i + len(nums) / 4]”, does that mean we should return true?
I was trying to apply this to my binary search and was not thinking straight so the hint went over my head… Retrospectively it is trivial, however I only see how to apply this with a sliding window:
limit = len(nums) // 4
for i in range(limit, len(nums)):
if nums[i] == nums[i-limit]:
return True
return False
Is it what the interviewer meant? Or is there a better, non-linear solution?
Nab is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
A number that appears more than n/4 times in nums must be one of the elements of nums[::len(nums)//4]. For each candidate number, we perform a binary search for the first position where it appears, and check whether the same number appears len(nums)//4 spots later:
import bisect
def check(nums):
n = len(nums)
assert n % 4 == 0
for i in nums[::n//4]:
first_appearance = bisect.bisect_left(nums, i)
if first_appearance + n//4 < len(nums) and nums[first_appearance + n//4] == i:
return True
return False
We perform at most 4 binary searches, and at most a constant amount of other work, so the time complexity is O(log n).
Since the array is sorted, if a number appears more than n/4 times, it will span a block of length greater than n/4.
Therefore, there will be at least one index i where the number at i is the same as the number at i + n/4.
Instead of iterating through every element, you can check positions spaced n/4 apart.
#Edited
def appears_more_than_n_over_4(nums):
n = len(nums)
limit = n // 4
check_positions = [0, limit, 2 * limit, 3 * limit]
for i in check_positions:
# Find the start and end of the current element
start = bisect.bisect_left(nums, nums[i])
end = bisect.bisect_right(nums, nums[i]) - 1
# Check if the count of the element exceeds the limit
if end - start + 1 > limit:
return True
return False
1