LogoKode$word

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

Learn how to find the only element with frequency less than K in a sorted array using a simple frequency-tracking approach in Java.

Krishna Shrivastava
1 views
LinkedInGithubX
0
0
Amazon OAAmazon Online AssessmentJavaArraysFrequency CountingSorted ArrayDSAArray Problems
Amazon OA: Find the Element Occurring Less Than K Times in a Sorted Array – Java Solution
Listen to articleAudio version
Ad

Introduction

This 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 = 3

Here:

2 → 3 times
3 → 2 times
4 → 3 times
5 → 3 times

Therefore, the answer is:

3

because 3 occurs fewer than K = 3 times.

Question

You 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.

Constraints

N <= 100000
K >= 2
1 <= B[i] <= 10000000000

Since B[i] can be as large as 10^10, a Java long should be used to safely store the array values.

Example

Consider:

B = [2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5]
K = 3

Frequency table:

Element Frequency
2 3
3 2
4 3
5 3

Only 3 occurs fewer than K times.

Therefore:

Output: 3

Understanding the Sorted Array

The 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 4

We 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 1

When we encounter 2, we know that:

1 occurred 3 times

We 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 Frequency

We can maintain two variables:

int cand;
int count;

where:

  1. cand represents the current element.
  2. 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 Element

If:

cand == arr[i]

then the current element is still being counted.

So:

count++;

Case 2: Element Changes and Frequency Is K

If:

cand != arr[i] && count == k

then 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 K

If:

cand != arr[i] && count < k

then the previous element is the unique element whose frequency is less than K.

So we can immediately stop.

Java Solution

The 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 Run

Consider:

arr = [1, 1, 2, 2, 2, 3, 3, 3]
k = 3

Initially:

cand = 1
count = 1

Now process the array.

Step 1

Current value:

arr[1] = 1

It is the same as cand.

count = 2

Step 2

Current value:

arr[2] = 2

The value changed.

Before moving to 2, we check the frequency of 1:

count = 2
k = 3

Since:

2 < 3

we have found the answer.

Therefore:

Output: 1

Another Example

Consider:

B = [2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5]
K = 3

We start with:

cand = 2
count = 1

After processing the three 2s:

cand = 2
count = 3

The next value is 3.

Since:

count == K

we move to the next candidate:

cand = 3
count = 1

After processing the second 3:

cand = 3
count = 2

The next value is 4.

Now:

count < K

because:

2 < 3

Therefore:

3

is the required answer.

Important Edge Case: Answer at the End

There 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 = 3

When 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 Analysis

We 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 <= 100000

and 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 2

In 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 4

all occurrences of an element form one continuous block.

That is what allows us to solve the problem with:

O(N) time
O(1) extra space

A Simpler Alternative

Because 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 found

Interview Tip

When 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:

HashMap

or sorting the array again, we can simply maintain a running frequency.

The important pattern is:

Current value
+
Consecutive frequency
+
Check when value changes

This pattern is useful in many array problems involving duplicate or repeated elements.

Conclusion

This 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 element
current frequency

Whenever 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.

Related Articles

Length of Longest Subarray With At Most K Frequency – Sliding Window Approach

Length of Longest Subarray With At Most K Frequency – Sliding Window Approach

Learn how to find the longest contiguous subarray where each element occurs at most K times using HashMap and sliding window.

Read Article
Unique Number of Occurrences

Unique Number of Occurrences

LeetCode Question 1207

Read Article
Intersection of Two Arrays II

Intersection of Two Arrays II

Leetcode question 350

Read Article
LeetCode 2784: Check if Array is Good – Java HashMap Solution Explained

LeetCode 2784: Check if Array is Good – Java HashMap Solution Explained

Learn how to solve LeetCode 2784 Check if Array is Good using HashMap and counting techniques in Java. Includes brute force intuition, optimized approach, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
Ai Assistant Kas