Total Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)

Try Our Full Platform: https://nas.io/backtobackswe 📹 Intuitive Video Explanations ❓New Unseen Questions 🔎 Get All Solutions Question: Given a sorted array, find the total count of occurrences of a given value K as efficiently as possible. (Hint: The best answer runs in O(log(n)) time) This was a question that I got in my 1st round Facebook interview. Error: At 3:27 the "Answer" should have said 1. Sorry. Approach 1: Linear scan and count Time: O(N) Space: O(1) Remember: whenever an array is sorted it automatically unlocks binary search which is very fast. Binary search should be first on your mind and you should tell your interviewer so immediately. Binary search operates off what is called an invariant. Our invariant is that no matter how often we split the search space, the space will stay sorted and hence again binary search can be used on it (doesn't have to be perfectly sorted though as we will see in other problems) Approach 2: Binary search for the first element and then linear scan to count the elements from that first element to its last occurrence. Average Case Time: O(log(n)) Space: O(1) Worst Case Time: O(N) Space: O(1) [O(log(n) if the binary search is recursive] This is the approach that I was stuck on, but my interviewer then said, "Can we keep it log(n) in every case?" Then I knew that we would only be dealing with binary searches, any linear scans would be unnecessary I knew I needed to get the count somehow so it occurred to me...if it is sorted, the lastOccurrence will give us the count if we just subtract the first occurrence from it and add 1. That is the total elements between the first and last occurrence and they all must be that number itself since the array is sorted Approach 3: Binary search for the first occurrence. If not found then return 0 occurrences total. If found, binary search for the 2nd element. The answer is: lastOccurrence - firstOccurrence + 1 Time: O(log(n)) + O(log(n)) = O(log(n)) Space: O(1) [O(log(