Count Occurrences in Sorted Array

▶

Steps

setup

Initialize first binary search for target

Set initial search boundaries lo=0 and hi=7 (length of array) to find left insertion point of target=2.

💡 Starting with the full array ensures we consider all possible positions for the target.

Line:

left = bisect.bisect_left(nums, target)

💡 The search space covers the entire array initially.

compare

Calculate mid index and compare mid_value with target

Calculate mid = (0 + 7) // 2 = 3, mid_value = nums[3] = 2, compare mid_value with target=2.

💡 Mid index splits the search space; comparison decides which half to keep.

Line:

mid = (lo + hi) // 2
mid_value = nums[mid]
if mid_value < target:

💡 Since mid_value equals target, we move hi to mid to find the leftmost occurrence.

compare

Calculate new mid and compare again

Calculate mid = (0 + 3) // 2 = 1, mid_value = nums[1] = 2, compare with target=2.

💡 Narrowing search space to left half to find left boundary.

Line:

mid = (lo + hi) // 2
mid_value = nums[mid]
if mid_value < target:

💡 Still found target, so continue moving hi left to find earliest occurrence.

compare

Calculate new mid and compare again

Calculate mid = (0 + 1) // 2 = 0, mid_value = nums[0] = 1, compare with target=2.

💡 Checking if target is to the right since mid_value < target.

Line:

mid = (lo + hi) // 2
mid_value = nums[mid]
if mid_value < target:

💡 Since mid_value is less than target, left boundary must be to the right.

compare

Search space narrowed to single index

Now lo=1 and hi=1, search space size is 0, binary search ends with left insertion point at index 1.

💡 When lo equals hi, the insertion point is found.

Line:

left = bisect.bisect_left(nums, target)  # returns lo

💡 Left insertion point for target=2 is index 1.

setup

Initialize second binary search for target+1

Set initial search boundaries lo=0 and hi=7 to find left insertion point of target+1=3.

💡 We repeat binary search to find the boundary for the next integer after target.

Line:

right = bisect.bisect_left(nums, target + 1)

💡 Starting fresh search space for target+1.

compare

Calculate mid and compare mid_value with target+1

Calculate mid = (0 + 7) // 2 = 3, mid_value = nums[3] = 2, compare with target=3.

💡 Mid value less than target+1 means search right half.

Line:

mid = (lo + hi) // 2
mid_value = nums[mid]
if mid_value < target:

💡 Since 2 < 3, left insertion point must be to the right.

compare

Calculate new mid and compare again

Calculate mid = (4 + 7) // 2 = 5, mid_value = nums[5] = 4, compare with target=3.

💡 Mid value greater than target means search left half.

Line:

mid = (lo + hi) // 2
mid_value = nums[mid]
if mid_value < target:

💡 Since 4 > 3, insertion point is to the left.

compare

Calculate new mid and compare again

Calculate mid = (4 + 5) // 2 = 4, mid_value = nums[4] = 3, compare with target=3.

💡 Mid value equals target means move hi to mid to find left insertion point.

Line:

mid = (lo + hi) // 2
mid_value = nums[mid]
if mid_value < target:

💡 We continue searching left to find earliest insertion point for 3.

compare

Search space narrowed to single index for target+1

Now lo=4 and hi=4, binary search ends with left insertion point for target+1=3 at index 4.

💡 Insertion point found where 3 would be inserted.

Line:

right = bisect.bisect_left(nums, target + 1)  # returns lo

💡 Left insertion point for target+1=3 is index 4.

prune

Calculate count of target occurrences

Subtract left insertion point (1) from right insertion point (4) to get count = 3.

💡 Difference between insertion points equals number of target occurrences.

Line:

return right - left

💡 Count of target=2 in array is 3.

import bisect

def count_occurrences(nums, target):
    # STEP 1: Find left insertion point of target
    left = bisect.bisect_left(nums, target)  # STEP 1-5
    # STEP 6: Find left insertion point of target+1
    right = bisect.bisect_left(nums, target + 1)  # STEP 6-10
    # STEP 11: Calculate count
    return right - left

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

📊

Count Occurrences in Sorted Array - Watch the Algorithm Execute, Step by Step

Watching each binary search step reveals how the search space shrinks and how the algorithm pinpoints the exact boundaries of the target values efficiently.

Target: 2

lo

1

0

2

1

2

2

2

3

3

4

4

5

5

6

Next: lo=0 hi=7

Target: 2

lo

1

0

2

1

2

2

mid

2

3

3

4

4

5

5

6

mid[3]=2 - mid_value == target, move hi to mid

Next: lo=0 hi=3

Target: 2

lo

1

0

mid

2

1

2

2

hi

2

3

3

4

4

5

5

6

mid[1]=2 - mid_value == target, move hi to mid

Next: lo=0 hi=1

Target: 2

lo/mid

1

0

hi

2

1

2

2

2

3

3

4

4

5

5

6

mid[0]=1 - mid_value < target, move lo to mid+1

Next: lo=1 hi=1

Target: 2

1

0

lo/hi

2

1

2

2

2

3

3

4

4

5

5

6

Next: lo=1 hi=1

Target: 3

lo

1

0

2

1

2

2

2

3

3

4

4

5

5

6

Next: lo=0 hi=7

Target: 3

lo

1

0

2

1

2

2

mid

2

3

3

4

4

5

5

6

mid[3]=2 - mid_value < target, move lo to mid+1

Next: lo=4 hi=7

Target: 3

1

0

2

1

2

2

2

3

lo

3

4

mid

4

5

5

6

mid[5]=4 - mid_value > target, move hi to mid

Next: lo=4 hi=5

Target: 3

1

0

2

1

2

2

2

3

lo/mid

3

4

hi

4

5

5

6

mid[4]=3 - mid_value == target, move hi to mid

Next: lo=4 hi=4

Target: 3

1

0

2

1

2

2

2

3

lo/hi

3

4

4

5

5

6

Next: lo=4 hi=4

Target: 2

1

0

2

1

2

2

2

3

3

4

4

5

5

6

Key Takeaways

✓ Binary search can be used twice to find the exact boundaries of a target value in a sorted array.

This insight is hard to see from code alone because the two searches look similar but serve different boundary-finding purposes.

✓ The difference between the left insertion points of target and target+1 gives the count of target occurrences efficiently.

Understanding this arithmetic relationship is easier when visualizing the insertion points rather than scanning the array.

✓ Each binary search step eliminates half the search space by comparing mid_value with the target, honing in on the left boundary.

Seeing how lo and hi move step-by-step clarifies why binary search is O(log n) and how it finds boundaries precisely.

Practice

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

2. Consider the following code snippet implementing the optimal binary search to find the single element in a sorted array where every other element appears twice. What is the returned value when the input is [1,1,2,3,3]?

easy

A. 3

B. 1

C. 2

D. Error due to index out of range

Solution

1. Step 1: Trace first iteration with low=0, high=4

   mid = 2 (even), nums[2]=2, nums[3]=3 not equal, so high = mid = 2

2. Step 2: Trace second iteration with low=0, high=2

   mid = 1 (odd), nums[1]=1, nums[0]=1 equal, so low = mid + 1 = 2

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Loop ends with low=2, nums[2]=2 returned [OK]

Hint: Check parity and compare adjacent elements carefully [OK]

Common Mistakes:

• Off-by-one errors in mid calculation
• Confusing even/odd parity logic
• Assuming index out of range error

3. What is the time complexity of the optimal approach that uses a single binary search followed by expanding boundaries to find the first and last positions of the target in a sorted array?

medium

A. O(n)

B. O(log n + k), where k is the number of occurrences of the target

C. O(log n * k), where k is the number of occurrences of the target

D. O(log n)

Solution

1. Step 1: Analyze binary search phase

   Binary search runs in O(log n) to find one occurrence of target.

2. Step 2: Analyze boundary expansion phase

   Expanding left and right to find all occurrences takes O(k), where k is count of target.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Combined complexity is O(log n + k), not multiplicative [OK]

Hint: Binary search plus linear expansion over occurrences [OK]

Common Mistakes:

• Assuming O(log n) only
• Multiplying log n by k incorrectly
• Ignoring expansion cost

4. Suppose the array is no longer sorted but you still need to find the first and last positions of a target value. Which approach is correct and efficient?

hard

A. Use a linear scan to find first and last occurrences directly

B. Sort the array first, then apply modified binary search to find positions

C. Use the same modified binary search approach since it works on any array

D. Use a hash map to store all indices of each value, then retrieve target positions

Solution

1. Step 1: Recognize that binary search requires sorted array

   Without sorting, binary search cannot guarantee correct positions.

2. Step 2: Evaluate alternatives

   Sorting changes indices, so linear scan or hash map are options; linear scan is simplest and O(n).

3. Step 3: Compare efficiency and correctness

   Linear scan finds first and last positions in one pass without modifying array.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Binary search requires sorted input; linear scan works otherwise [OK]

Hint: Binary search needs sorted array; linear scan works otherwise [OK]

Common Mistakes:

• Trying binary search on unsorted array
• Sorting and losing original indices
• Overcomplicating with hash maps

5. Suppose the matrix rows are sorted but columns are not guaranteed to be sorted. Which of the following approaches correctly finds the target value efficiently?

hard

A. Use the staircase search starting from the top-right corner.

B. Use a brute force nested loop to check every element.

C. Perform binary search on each row independently.

D. Sort each column first, then apply staircase search.

Solution

1. Step 1: Understand matrix constraints

   Only rows are sorted; columns are unsorted, so staircase search assumptions fail.

2. Step 2: Evaluate approaches

   Binary search on rows works but columns unsorted means target could be anywhere in columns; brute force guarantees correctness.

3. Step 3: Consider sorting columns

   Sorting columns is expensive and changes matrix; not practical for search.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Brute force is correct though less efficient; others rely on column sorting [OK]

Hint: Without column sorting, staircase search fails [OK]

Common Mistakes:

• Assuming staircase search works with only row sorting
• Thinking sorting columns is cheap
• Believing binary search on rows suffices