Count Occurrences of Element in Sorted Array in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main advantage of using a sorted array to count occurrences of an element?

A sorted array allows us to use binary search to quickly find the first and last positions of the element, making counting efficient.

beginner

Explain how binary search helps in counting occurrences of an element in a sorted array.

Binary search finds the first and last positions of the element in the array. The count is last position minus first position plus one.

intermediate

What is the time complexity of counting occurrences of an element in a sorted array using binary search?

The time complexity is O(log n) because binary search is used twice to find the first and last positions.

beginner

Why is a linear scan not efficient for counting occurrences in a large sorted array?

A linear scan checks each element one by one, which takes O(n) time, slower than binary search's O(log n) for large arrays.

beginner

What happens if the element is not present in the sorted array when counting occurrences?

Both first and last position searches return -1 or invalid indices, so the count is zero.

What is the first step to count occurrences of an element in a sorted array?

A Find the first occurrence of the element using binary search

B Scan the entire array linearly

C Sort the array again

D Remove duplicates from the array

Finding the first occurrence using binary search helps locate where the element starts.

If the first occurrence of an element is at index 3 and last occurrence at index 7, what is the count?

A 4

B 3

C 5

D 7

Count = last index - first index + 1 = 7 - 3 + 1 = 5.

What is the time complexity of counting occurrences using binary search twice?

A O(log n)

B O(n)

C O(n log n)

D O(1)

Each binary search takes O(log n), so total is O(log n).

What should you return if the element is not found in the array?

A The length of the array

B The first index

C -1

D Zero

If element is not found, occurrences count is zero.

Why is binary search preferred over linear scan for large sorted arrays?

A Binary search is simpler to implement

B Binary search is faster with O(log n) time

C Linear scan uses less memory

D Linear scan is faster

Binary search is faster because it reduces search space quickly.

Describe the steps to count occurrences of an element in a sorted array using binary search.

Think about how to find boundaries of the element in the array.

Explain why counting occurrences in a sorted array is more efficient with binary search than with a linear scan.

Compare how many elements each method checks.

Practice

1. What does the problem "Count Occurrences of Element in Sorted Array" ask you to find?

easy

A. The number of times a given element appears in a sorted array

B. The sum of all elements in the array

C. The largest element in the array

D. The position of the first element in the array

Solution

1. Step 1: Understand the problem statement

   The problem asks to find how many times a specific element appears in a sorted array.

2. Step 2: Identify the required output

   The output is the count of occurrences of that element, not its position or sum.

3. Final Answer:

   The number of times a given element appears in a sorted array -> Option A

4. Quick Check:

   Count occurrences = number of times element appears [OK]

Hint: Count how many times the element repeats in the sorted list [OK]

Common Mistakes:

• Confusing count with element position
• Trying to sum elements instead of counting
• Ignoring that array is sorted

2. Which of the following Python code snippets correctly counts occurrences of x in a sorted list arr using built-in methods?

easy

A. count = arr.find(x)

B. count = arr.count(x)

C. count = arr.index(x)

D. count = arr.length(x)

Solution

1. Step 1: Recall Python list methods

   count() returns how many times an element appears in a list.

2. Step 2: Check other methods

   find() and index() find positions, not counts; length() is invalid.

3. Final Answer:

   count = arr.count(x) -> Option B

4. Quick Check:

   Use count() to get occurrences [OK]

Hint: Use list.count(element) to get occurrences fast [OK]

Common Mistakes:

• Using index() instead of count()
• Trying to use find() which is for strings
• Using length() which is not a list method

3. What is the output of the following code?

def count_occurrences(arr, x):
    return arr.count(x)

arr = [1, 2, 2, 2, 3, 4]
x = 2
print(count_occurrences(arr, x))

medium

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Understand the input array and element

   The array is [1, 2, 2, 2, 3, 4] and the element to count is 2.

2. Step 2: Count occurrences of 2 in the array

   2 appears three times in the array.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count of 2 in array = 3 [OK]

Hint: Count how many times 2 appears in the list [OK]

Common Mistakes:

• Counting unique elements instead of occurrences
• Miscounting the number of 2s
• Confusing count with index

4. Find the error in this code that tries to count occurrences of x in a sorted array arr:

def count_occurrences(arr, x):
    count = 0
    for i in range(len(arr)):
        if arr[i] == x:
            count += 1
        else:
            break
    return count

arr = [1, 2, 2, 2, 3, 4]
x = 2
print(count_occurrences(arr, x))

medium

A. The loop breaks too early, missing some occurrences

B. The count variable is not initialized

C. The function does not return any value

D. The comparison operator is incorrect

Solution

1. Step 1: Analyze the loop and break condition

   The loop breaks on first element not equal to x, so it counts only consecutive occurrences from start.

2. Step 2: Check the input array and x

   Since x=2 and array starts with 1, the loop breaks immediately, count remains 0.

3. Final Answer:

   The loop breaks too early, missing some occurrences -> Option A

4. Quick Check:

   Break stops counting early, so count is wrong [OK]

Hint: Don't break loop; count all matching elements [OK]

Common Mistakes:

• Breaking loop on first non-match in unsorted array
• Not counting all occurrences
• Assuming array starts with x

5. Given a sorted array arr = [1, 2, 2, 2, 3, 4, 4, 5], which approach efficiently counts occurrences of x = 4 without scanning the entire array?

hard

A. Use a for loop to count all 4s by scanning from start to end

B. Use arr.count(4) which scans entire array internally

C. Use binary search to find first and last positions of 4, then calculate count

D. Sort the array again and count 4s

Solution

1. Step 1: Understand the array is sorted

   Since the array is sorted, all 4s are together in a block.

2. Step 2: Use binary search to find first and last occurrence

   Binary search finds first and last index of 4 quickly, then count = last - first + 1.

3. Step 3: Compare other options

   For loop and count() scan entire array, sorting again is unnecessary and inefficient.

4. Final Answer:

   Use binary search to find first and last positions of 4, then calculate count -> Option C

5. Quick Check:

   Binary search + index difference = count [OK]

Hint: Find first and last index with binary search, subtract [OK]

Common Mistakes:

• Scanning entire array instead of using binary search
• Sorting array again unnecessarily
• Using count() without considering efficiency