Count Occurrences in Sorted Array

📋

Count Occurrences in Sorted Array

Edge cases:

</>

IDE

def count_occurrences(nums: list[int], target: int) -> int:public int countOccurrences(int[] nums, int target)int countOccurrences(const vector<int>& nums, int target)function countOccurrences(nums, target)

def count_occurrences(nums, target):
    # Write your solution here
    pass

class Solution {
    public int countOccurrences(int[] nums, int target) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int countOccurrences(const vector<int>& nums, int target) {
    // Write your solution here
    return 0;
}

function countOccurrences(nums, target) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Binary search only finds one occurrence or fails to find target when present.✅ Implement two binary searches to find leftmost and rightmost indices of target.

Wrong: n (array length)Returning array length without checking if all elements equal target.✅ Verify target presence by binary search before returning count.

Wrong: Incorrect count off by oneOff-by-one error in count calculation (missing +1).✅ Count = right boundary - left boundary + 1.

Wrong: Non-zero count for target not in arrayNot checking if target is actually present between boundaries.✅ Check if nums[left] == target before returning count; else return 0.

Wrong: Timeout (TLE)Using linear scan instead of binary search on large inputs.✅ Use binary search to find leftmost and rightmost indices for O(log n) complexity.

✓

Test Cases

Try testing your code on empty and single-element arrays to catch base case bugs.

Focus on boundary conditions and off-by-one errors in your binary search implementation.

Optimize your solution to use binary search for O(log n) performance on large inputs.

t1_01basic

Input{"nums":[1,2,2,2,3,4,5],"target":2}

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Think about how binary search can find boundaries instead of just presence.

💡 Use binary search to find the leftmost and rightmost positions of the target.

💡 Count = rightmost index - leftmost index + 1 if target found; else 0.

Why it failed: Incorrect count likely due to not finding both leftmost and rightmost occurrences. Fix by implementing two binary searches: one for left boundary and one for right boundary.

✓ Correctly counts occurrences using boundary binary searches.

t1_02basic

Input{"nums":[1,1,2,2,2,2,3,3,4],"target":3}

Expected2

⏱ Performance - must finish in 2000ms

The number 3 appears twice at indices 6 and 7.

💡 Check if your binary search correctly identifies the first and last positions of the target.

💡 Remember to handle duplicates by searching for boundaries, not just any occurrence.

💡 Return right boundary - left boundary + 1 as the count.

Why it failed: Counting all occurrences by scanning linearly is inefficient; missing boundary search causes wrong counts. Fix by using two binary searches for leftmost and rightmost indices.

✓ Efficiently finds count by locating boundaries with binary search.

t2_01edge

Input{"nums":[],"target":5}

Expected0

⏱ Performance - must finish in 2000ms

Empty array contains no elements, so count is 0.

💡 Consider what happens when the array is empty.

💡 Binary search should immediately return no occurrence if array length is zero.

💡 Return 0 if array is empty or target not found.

Why it failed: Code crashes or returns non-zero on empty input due to missing empty check. Fix by adding a condition to handle empty arrays before binary search.

✓ Handles empty array correctly by returning 0.

t2_02edge

Input{"nums":[10],"target":10}

Expected1

⏱ Performance - must finish in 2000ms

Single element array where target equals the element, count is 1.

💡 Test your binary search on single-element arrays.

💡 Check if your code correctly identifies the target when array length is 1.

💡 Return 1 if the single element matches the target.

Why it failed: Fails to handle single-element arrays correctly, possibly due to boundary conditions in binary search. Fix by ensuring binary search works for arrays of length 1.

✓ Correctly counts target in single-element array.

t2_03edge

Input{"nums":[2,2,2,2,2],"target":2}

Expected5

⏱ Performance - must finish in 2000ms

All elements are the target, so count equals array length 5.

💡 Check if your binary search finds the full range when all elements are equal to target.

💡 Left boundary should be 0 and right boundary should be n-1 in this case.

💡 Count is right boundary - left boundary + 1 = 5.

Why it failed: Fails to find correct boundaries when all elements are target, possibly returning partial range. Fix by ensuring binary search correctly finds leftmost and rightmost indices even when all elements match.

✓ Correctly counts all elements when all equal target.

t2_04edge

Input{"nums":[1,2,3,4,5],"target":3}

Expected1

⏱ Performance - must finish in 2000ms

Target appears exactly once in the middle of the array.

💡 Check if your binary search can find a single occurrence in the middle.

💡 Ensure boundaries are correctly identified even if only one occurrence exists.

💡 Count should be 1 when left and right boundaries are equal.

Why it failed: Fails to handle single occurrence correctly, possibly returning 0 or more than 1. Fix by ensuring count calculation handles left == right case properly.

✓ Correctly counts single occurrence in the array.

t3_01corner

Input{"nums":[1,2,3,4,5],"target":6}

Expected0

⏱ Performance - must finish in 2000ms

Target 6 is larger than all elements, so count is 0.

💡 Check how your binary search behaves when target is greater than all elements.

💡 Ensure binary search returns no occurrence if target not found.

💡 Return 0 if left boundary > right boundary or target not present.

Why it failed: Returns non-zero count when target is larger than all elements due to incorrect boundary checks. Fix by verifying that left boundary <= right boundary before counting.

✓ Correctly returns 0 when target is larger than all elements.

t3_02corner

Input{"nums":[1,2,3,4,5],"target":0}

Expected0

⏱ Performance - must finish in 2000ms

Target 0 is smaller than all elements, so count is 0.

💡 Check how your binary search behaves when target is smaller than all elements.

💡 Ensure binary search returns no occurrence if target not found.

💡 Return 0 if left boundary > right boundary or target not present.

Why it failed: Returns non-zero count when target is smaller than all elements due to incorrect boundary checks. Fix by verifying that left boundary <= right boundary before counting.

✓ Correctly returns 0 when target is smaller than all elements.

t3_03corner

Input{"nums":[1,2,2,2,3,4,5],"target":2}

Expected3

⏱ Performance - must finish in 2000ms

Test to catch off-by-one errors in boundary calculations for target 2.

💡 Check if your binary search correctly handles inclusive boundaries.

💡 Verify that right boundary index is included in count calculation.

💡 Count = right boundary - left boundary + 1; off-by-one errors cause wrong counts.

Why it failed: Off-by-one error in count calculation, e.g. missing +1 in count formula. Fix by adding +1 to (right - left) when computing count.

✓ Correctly handles inclusive boundaries and counts occurrences.

t4_01performance

Input{"nums":[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9],"target":5}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100, O(log n) binary search must complete within 2 seconds.

💡 Linear scan O(n) will time out on large inputs.

💡 Use binary search to achieve O(log n) time complexity.

💡 Implement two binary searches to find leftmost and rightmost indices efficiently.

Why it failed: Solution times out due to linear scan or inefficient approach. Fix by using binary search for boundaries to achieve O(log n) complexity.

✓ Efficient binary search approach confirmed by passing performance test.

Practice

1. You are given a sorted array and need to efficiently find the index of a target value or determine it is not present. Which algorithmic approach guarantees the fastest search in O(log n) time by repeatedly dividing the search interval in half?

easy

A. Linear search by scanning each element until the target is found

B. Greedy algorithm selecting the closest element at each step

C. Binary search by repeatedly halving the search range based on comparisons

D. Dynamic programming to build a table of subproblems for target lookup

Solution

1. Step 1: Understand problem constraints

   The array is sorted, enabling divide-and-conquer strategies.

2. Step 2: Identify algorithm matching O(log n) search

   Binary search halves the search space each step, guaranteeing O(log n) time, unlike linear or greedy approaches.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search is the classic O(log n) search on sorted arrays [OK]

Hint: Sorted array + fast search -> binary search [OK]

Common Mistakes:

• Confusing greedy or DP with binary search
• Assuming linear scan is optimal
• Thinking DP applies to simple search

2. You are given a sorted array and a target value. You need to find the starting and ending indices of the target value in the array. Which algorithmic approach guarantees an optimal solution with logarithmic time complexity?

easy

A. Linear scan from start to end to find first and last occurrences

B. Greedy approach to jump to target positions based on value comparisons

C. Modified binary search to find leftmost and rightmost positions separately

D. Dynamic programming to store intermediate results for each index

Solution

1. Step 1: Understand problem constraints

   The array is sorted, so binary search can be used to find target positions efficiently.

2. Step 2: Identify suitable algorithm

   Modified binary search can find leftmost and rightmost indices in O(log n) time, which is optimal compared to linear scan or greedy methods.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search exploits sorted property for O(log n) search [OK]

Hint: Sorted array + position search -> modified binary search [OK]

Common Mistakes:

• Thinking linear scan is optimal
• Confusing greedy with binary search
• Using DP unnecessarily

3. What is the time complexity of the recursive modified binary search algorithm for finding a peak element in an array of size n, and why might some candidates mistakenly think it is worse?

medium

A. O(n) because each recursive call processes a subarray of size n-1

B. O(log n) because each recursive call halves the search space

C. O(n log n) because recursion adds a log n factor to linear scanning

D. O(log n) time but O(n) space due to recursion stack

Solution

1. Step 1: Analyze recursive calls

   Each call halves the search space, so number of calls is O(log n).

2. Step 2: Confirm work per call

   Each call does O(1) work (simple comparisons), so total time is O(log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Halving search space leads to logarithmic time [OK]

Hint: Halving input size -> O(log n) time [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming linear scan inside recursion
• Thinking recursion multiplies complexity

4. Examine the following buggy code that attempts to search a target in a 2D matrix using the staircase search approach starting from the top-left corner. Identify the line containing the subtle bug that causes incorrect behavior or infinite loops.

medium

A. Line 9: Incrementing row when element is less than target

B. Line 7: Using '<' instead of '<=' in while condition

C. Line 11: Decrementing col without boundary check

D. Line 3: Starting at top-left corner instead of top-right

Solution

1. Step 1: Analyze starting point

   Starting at top-left corner breaks the staircase search logic because we cannot eliminate rows or columns correctly.

2. Step 2: Check pointer movements

   Moving row down when current < target and col left when current > target only works if starting at top-right corner.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Starting at top-left causes infinite loops or wrong results [OK]

Hint: Staircase search must start at top-right corner [OK]

Common Mistakes:

• Starting at top-left or bottom-left corner
• Not checking empty matrix
• Moving pointers in wrong directions

5. Consider the following buggy code snippet for finding the pivot in a rotated sorted array. Which line contains the subtle bug that can cause incorrect pivot detection?

medium

A. if nums[mid] > nums[high]: -- comparison logic is correct

B. mid = (low + high) / 2 -- mid should be integer index, not float

C. low = mid + 1 -- updating low is correct when nums[mid] > nums[high]

D. return low -- returning low as pivot is correct

Solution

1. Step 1: Identify mid calculation issue

   mid is computed using division '/', which returns float in Python 3, causing invalid indexing.

2. Step 2: Impact of float mid

   Using float as index causes runtime error or incorrect behavior; integer division '//' is required.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Changing '/' to '//' fixes the bug [OK]

Hint: mid must be integer index [OK]

Common Mistakes:

• Using '/' instead of '//' in Python
• Misplaced comparison operators