Count Occurrences of Element in Sorted Array in DSA Python - Build from Scratch

Count Occurrences of Element in Sorted Array

📖 Scenario: You have a sorted list of product IDs representing items sold in a store. You want to find out how many times a specific product ID appears in the sales list.

🎯 Goal: Build a program that counts how many times a given product ID appears in a sorted list of product IDs.

📋 What You'll Learn

Create a sorted list of product IDs with exact values

Create a variable to hold the product ID to count

Use a loop to count occurrences of the product ID in the list

Print the count of occurrences

💡 Why This Matters

🌍 Real World

Counting occurrences of items in sorted lists is common in sales data analysis, inventory checks, and search results.

💼 Career

This skill helps in data analysis roles, software development for inventory systems, and any job requiring data processing.

1

Create the sorted list of product IDs

Create a list called product_ids with these exact sorted values: [101, 101, 102, 103, 103, 103, 104, 105]

DSA Python

# Create the sorted list of product IDs
# Your code here

Hint

Use square brackets [] to create a list and separate values with commas.

2

Set the product ID to count

Create a variable called target_id and set it to 103 to represent the product ID you want to count.

DSA Python

product_ids = [101, 101, 102, 103, 103, 103, 104, 105]
# Create the target product ID to count
# Your code here

Hint

Use the assignment operator = to set the value.

3

Count occurrences of the target product ID

Create a variable called count and set it to 0. Then use a for loop with variable pid to iterate over product_ids. Inside the loop, increase count by 1 each time pid equals target_id.

DSA Python

product_ids = [101, 101, 102, 103, 103, 103, 104, 105]
target_id = 103
# Count how many times target_id appears in product_ids
# Your code here

Hint

Use count = 0 before the loop. Inside the loop, use an if statement to check equality and add 1 to count.

4

Print the count of occurrences

Use print() to display the value of count.

DSA Python

product_ids = [101, 101, 102, 103, 103, 103, 104, 105]
target_id = 103
count = 0
for pid in product_ids:
    if pid == target_id:
        count += 1
# Print the count of target_id
# Your code here

Hint

Use print(count) to show the final count.

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