What happens if you using linear scan instead of binary search?

Code is too slow and may time out on large inputs Fix: Implement binary search to find boundaries

What happens if you not checking if target exists before calculating count?

Returns incorrect positive count when target not present Fix: Check if left boundary <= right boundary before returning count

What happens if you using mid = (left + right) / 2 without overflow protection?

Potential integer overflow in some languages Fix: Use mid = left + (right - left) / 2

Interview Prepmodified-binary-searcheasyAmazonGoogle

Count Occurrences in Sorted Array

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

easyBINARY_SEARCHAmazonGoogle

Imagine you have a sorted list of product IDs and want to quickly find how many times a particular product appears to manage inventory efficiently.

💡 This problem is about efficiently counting how many times a target appears in a sorted array. Beginners often struggle because they try to scan the entire array linearly, missing the power of binary search to find boundaries quickly.

📋

Problem Statement

Given a sorted array of integers and a target integer, return the number of times the target appears in the array. If the target is not present, return 0.

1 ≤ n ≤ 10^5-10^9 ≤ array elements, target ≤ 10^9Array is sorted in non-decreasing order

💡

Example

Input"nums = [1,2,2,2,3,4,5], target = 2"

Output3

The number 2 appears at indices 1, 2, and 3, so the count is 3.

Empty array → 0
Target smaller than all elements → 0
Target larger than all elements → 0
All elements are the target → n (length of array)

⚠️

Common Mistakes

Using linear scan instead of binary search

Code is too slow and may time out on large inputs

✅ Implement binary search to find boundaries

Incorrectly adjusting pointers in binary search (off-by-one errors)

Infinite loops or wrong boundaries found

✅ Carefully update left and right pointers and test edge cases

Not checking if target exists before calculating count

Returns incorrect positive count when target not present

✅ Check if left boundary <= right boundary before returning count

Using mid = (left + right) / 2 without overflow protection

Potential integer overflow in some languages

✅ Use mid = left + (right - left) / 2

Confusing bisect_left and bisect_right in Python

Incorrect count returned

✅ Use bisect_left for target and target+1 to get correct boundaries

🧠

Brute Force (Linear Scan)

💡 This approach exists to establish a baseline and ensure understanding of the problem before optimizing. It’s simple but inefficient for large inputs.

Intuition

Check every element in the array and count how many times the target appears.

Algorithm

Initialize a count to zero.
Iterate through each element in the array.
If the element equals the target, increment the count.
Return the count after the iteration completes.

💡 This algorithm is straightforward but can be slow because it checks every element even if the array is sorted.

</>

Code

def count_occurrences(nums, target):
    count = 0
    for num in nums:
        if num == target:
            count += 1
    return count

# Driver code
if __name__ == '__main__':
    nums = [1,2,2,2,3,4,5]
    target = 2
    print(count_occurrences(nums, target))  # Output: 3

Line Notes

count = 0Initialize count to track occurrences

for num in nums:Iterate over every element to check for target

if num == target:Check if current element matches target

count += 1Increment count when target found

public class CountOccurrences {
    public static int countOccurrences(int[] nums, int target) {
        int count = 0;
        for (int num : nums) {
            if (num == target) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,2,2,3,4,5};
        int target = 2;
        System.out.println(countOccurrences(nums, target)); // Output: 3
    }
}

Line Notes

int count = 0;Initialize count to zero before iteration

for (int num : nums)Loop through each element in the array

if (num == target)Check if current element equals target

count++;Increment count when target found

#include <iostream>
#include <vector>
using namespace std;

int countOccurrences(const vector<int>& nums, int target) {
    int count = 0;
    for (int num : nums) {
        if (num == target) {
            count++;
        }
    }
    return count;
}

int main() {
    vector<int> nums = {1,2,2,2,3,4,5};
    int target = 2;
    cout << countOccurrences(nums, target) << endl; // Output: 3
    return 0;
}

Line Notes

int count = 0;Initialize counter before loop

for (int num : nums)Range-based loop to check each element

if (num == target)Compare current element with target

count++;Increment count if target matches

function countOccurrences(nums, target) {
    let count = 0;
    for (const num of nums) {
        if (num === target) {
            count++;
        }
    }
    return count;
}

// Test
const nums = [1,2,2,2,3,4,5];
const target = 2;
console.log(countOccurrences(nums, target)); // Output: 3

Line Notes

let count = 0;Initialize count variable

for (const num of nums)Loop through each element in array

if (num === target)Check if element equals target

count++;Increment count when target found

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan through the entire array once, so time is linear in array size. Space is constant as we only store a count.

💡 For n=100,000 elements, this means 100,000 checks, which can be slow in interviews or large datasets.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large arrays, motivating better methods.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n)`	`O(1)`	No	N/A	Mention only - never code for large inputs
2. Binary Search for Boundaries	`O(log n)`	`O(1)`	No	N/A	Code this approach for best balance of speed and clarity
3. Built-in Binary Search Functions	`O(log n)`	`O(1)`	No	N/A	Use if allowed to simplify code and reduce bugs

Practice

(1/5)

1. Given the following code for finding a peak element, what is the final output when the input array is [1, 3, 2]?

def findPeakElement(nums):
    def binarySearch(low, high):
        if low == high:
            return low
        mid = (low + high) // 2
        if nums[mid] < nums[mid + 1]:
            return binarySearch(mid + 1, high)
        else:
            return binarySearch(low, mid)
    return binarySearch(0, len(nums) - 1)

print(findPeakElement([1, 3, 2]))

easy

A. None of the above

B. 0

C. 2

D. 1

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Trace first call binarySearch(0, 2)

Step 2: Trace second call binarySearch(0, 1)

Step 3: Trace third call binarySearch(1, 1)

Final Answer:

Quick Check:

Solution

Step 1: Initialize min-heap with first elements

Step 2: Extract elements until count == k

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Recognize the binary search pattern on answer space

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Recognize the pattern

Final Answer:

Quick Check:

Solution

Step 1: Analyze loop control variables

Step 2: Identify missing update

Final Answer:

Quick Check:

Ready to prove it?