Count Occurrences in Sorted Array
EasyupperBound − lowerBound
Find the first and last spot of a number; the count is just last − first + 1.
The idea
The count of x equals the gap between where it starts (lower bound) and where it ends (upper bound).
1
2
2
2
3
0
1
2
3
4
target2
Step 1 of 7. Brute force: scan the whole array counting 2. Values: 1, 2, 2, 2, 3. target 2.
1/7
Brute force
timeO(n)spaceO(1)
Scan and count.
1let count = 0;2for (let i = 0; i < n; i++)3 if (nums[i] === target) count++;4return count;Input
- array
- [1, 2, 2, 2, 3]
Memory
- i
- —
- target
- 2
Output
- count
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 2, 2, 3], target = 2
- Output:
- 3
- Explanation:
- 2 appears 3 times.
Example 2
- Input:
- nums = [1, 1, 2, 3], target = 1
- Output:
- 2
- Explanation:
- 1 appears twice.
Example 3
- Input:
- nums = [1, 2, 3], target = 5
- Output:
- 0
- Explanation:
- 5 is absent → 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.