Amazon OA: Find the Element Occurring Less Than K Times in a Sorted Array – Java Solution

IntroductionThis is a sorted array frequency problem that can appear in coding assessments and online assessments such as an Amazon OA.You are given a sorted array B of size N. Every distinct element occurs exactly K times except for one element, whose frequency is less than K.The task is to find that element.Because the array is sorted, all occurrences of the same element are located together. This allows us to process the array sequentially and keep track of the current element and its frequency.For example:B = [2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5]K = 3Here:2 → 3 times3 → 2 times4 → 3 times5 → 3 timesTherefore, the answer is:3because 3 occurs fewer than K = 3 times.QuestionYou are given a sorted array B of size N.Every element in the array occurs exactly K times except one element, which occurs fewer than K times.Find that element.It is guaranteed that there is exactly one element whose frequency is less than K.ConstraintsN <= 100000K >= 21 <= B[i] <= 10000000000Since B[i] can be as large as 10^10, a Java long should be used to safely store the array values.ExampleConsider:B = [2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5]K = 3Frequency table:Element Frequency2 33 24 35 3Only 3 occurs fewer than K times.Therefore:Output: 3Understanding the Sorted ArrayThe most important property of this problem is that the array is sorted.Because of that, identical elements always appear consecutively.For example:1 1 1 2 2 2 3 3 4 4 4We never have to search the entire array to count the occurrences of an element.We can simply scan from left to right.When the value changes, the frequency of the previous value is known.For example:1 1 1When we encounter 2, we know that:1 occurred 3 timesWe can compare this frequency with K.If it is less than K, then 1 is the required answer.Approach: Track the Current Element and Its FrequencyWe can maintain two variables:int cand;int count;where:cand represents the current element.count represents how many times that element has appeared so far.Initially:cand = arr[0];count = 1;Then we scan the remaining elements.There are three important situations.Case 1: Same ElementIf:cand == arr[i]then the current element is still being counted.So:count++;Case 2: Element Changes and Frequency Is KIf:cand != arr[i] && count == kthen the previous element occurred exactly K times.Therefore, we can start counting the new element:cand = arr[i];count = 1;Case 3: Element Changes and Frequency Is Less Than KIf:cand != arr[i] && count < kthen the previous element is the unique element whose frequency is less than K.So we can immediately stop.Java SolutionThe same logic can be implemented more cleanly as follows:class Main { public static void main(String[] args) { int[] arr = {1, 1, 2, 2, 2, 3, 3, 3}; int k = 3; int cand = arr[0]; int count = 1; for (int i = 1; i < arr.length; i++) { // Current element is still the same if (cand == arr[i]) { count++; } // Current element changed else { // Previous element occurred less than K times if (count < k) { break; } // Start counting the new element cand = arr[i]; count = 1; } } // The incomplete-frequency element may be the last element if (count < k) { System.out.println(cand); } }}Dry RunConsider:arr = [1, 1, 2, 2, 2, 3, 3, 3]k = 3Initially:cand = 1count = 1Now process the array.Step 1Current value:arr[1] = 1It is the same as cand.count = 2Step 2Current value:arr[2] = 2The value changed.Before moving to 2, we check the frequency of 1:count = 2k = 3Since:2 < 3we have found the answer.Therefore:Output: 1Another ExampleConsider:B = [2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5]K = 3We start with:cand = 2count = 1After processing the three 2s:cand = 2count = 3The next value is 3.Since:count == Kwe move to the next candidate:cand = 3count = 1After processing the second 3:cand = 3count = 2The next value is 4.Now:count < Kbecause:2 < 3Therefore:3is the required answer.Important Edge Case: Answer at the EndThere is one important case to handle.Suppose the incomplete element is the last element in the array.For example:arr = [1, 1, 1, 2, 2]K = 3When the loop finishes, there is no next element that causes the value to change.So the condition:if (cand != arr[i])will never execute for the final 2.We therefore need one final check after the loop:if (count < k) { System.out.println(cand);}This handles the case where the answer is at the end.Complexity AnalysisWe scan the array only once.For every element, we perform constant-time operations.Therefore:Time Complexity:O(N)Space Complexity:O(1)This is efficient enough for:N <= 100000and does not require an additional HashMap or frequency array.Why Does the Sorted Property Matter?Without the sorted property, the same element could appear at different positions.For example:2 3 2 4 3 2In that case, simply maintaining the frequency of the current consecutive value would not work.We would need another approach such as a HashMap.But because the input is sorted:2 2 2 3 3 4 4 4all occurrences of an element form one continuous block.That is what allows us to solve the problem with:O(N) timeO(1) extra spaceA Simpler AlternativeBecause the array is sorted, another straightforward solution is to count consecutive equal values.For example:class Main { public static void main(String[] args) { int[] arr = {2, 2, 2, 3, 3, 4, 4, 4}; int k = 3; int count = 1; for (int i = 1; i <= arr.length; i++) { if (i < arr.length && arr[i] == arr[i - 1]) { count++; } else { if (count < k) { System.out.println(arr[i - 1]); break; } count = 1; } } }}This version focuses directly on counting each consecutive group.The idea is:Read same values ↓Count them ↓Value changes ↓Check count < K ↓If yes → answer foundInterview TipWhen an interview or OA problem gives you a sorted array, always ask yourself:What does sorting allow me to avoid?Here, sorting means all equal values are adjacent.Instead of using:HashMapor sorting the array again, we can simply maintain a running frequency.The important pattern is:Current value+Consecutive frequency+Check when value changesThis pattern is useful in many array problems involving duplicate or repeated elements.ConclusionThis Amazon OA-style problem can be solved efficiently by taking advantage of the fact that the input array is sorted.Since equal elements appear consecutively, we only need to maintain:current elementcurrent frequencyWhenever the element changes, we check whether its frequency was less than K.The solution requires:Time: O(N)Space: O(1)The main takeaway is that the sorted property removes the need for additional frequency data structures and lets us find the unique incomplete-frequency element with a single linear scan.