Count Occurrences of Element in Sorted Array in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the first occurrence of the target in the sorted array.

DSA Python

def first_occurrence(arr, target):
    low, high = 0, len(arr) - 1
    result = -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            result = mid
            high = mid [1]
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result

Drag options to blanks, or click blank then click option'

A- 2

B+ 1

C- 1

D+ 2

Attempts:

3 left

💡 Hint

Common Mistakes

Moving high to mid + 1 causes infinite loop or wrong index.

Not updating high pointer after finding target.

When the target is found, to find the first occurrence, we move the high pointer to mid - 1 to continue searching in the left half.

2fill in blank

medium

Complete the code to find the last occurrence of the target in the sorted array.

DSA Python

def last_occurrence(arr, target):
    low, high = 0, len(arr) - 1
    result = -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            result = mid
            low = mid [1]
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result

Drag options to blanks, or click blank then click option'

A- 2

B- 1

C+ 2

D+ 1

Attempts:

3 left

💡 Hint

Common Mistakes

Moving low to mid - 1 causes infinite loop or wrong index.

Not updating low pointer after finding target.

When the target is found, to find the last occurrence, we move the low pointer to mid + 1 to continue searching in the right half.

3fill in blank

hard

Fix the error in the code to correctly count occurrences of the target in the sorted array.

DSA Python

def count_occurrences(arr, target):
    first = first_occurrence(arr, target)
    if first == -1:
        return 0
    last = last_occurrence(arr, target)
    return last - first [1] 1

Drag options to blanks, or click blank then click option'

A+

B-

C/

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Subtracting one instead of adding one.

Using multiplication or division instead of addition.

The count of occurrences is last index minus first index plus one.

4fill in blank

hard

Fill both blanks to create a dictionary of word lengths for words longer than 3 characters.

DSA Python

words = ['apple', 'bat', 'carrot', 'dog', 'elephant']
lengths = {word: [1] for word in words if len(word) [2] 3}

Drag options to blanks, or click blank then click option'

Alen(word)

B>

C<

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' causing wrong filtering.

Using word instead of len(word) for values.

We want the length of each word as the value and only include words longer than 3 characters.

5fill in blank

hard

Fill all three blanks to create a dictionary with uppercase keys, values as word lengths, and only words longer than 3 characters.

DSA Python

words = ['apple', 'bat', 'carrot', 'dog', 'elephant']
lengths = [1]: [2] for word in words if len(word) [3] 3}

Drag options to blanks, or click blank then click option'

Aword.upper()

Blen(word)

C>

Dword.lower()

Attempts:

3 left

💡 Hint

Common Mistakes

Using word.lower() instead of word.upper() for keys.

Using '<' instead of '>' for filtering.

Keys are uppercase words, values are their lengths, and only words longer than 3 are included.

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