Count How Many Times a Number Appears in a Sorted Array
Solve this Problem
Given an array
nums sorted in non-decreasing order and an integer target, return how many times target appears in nums.
Solve it in O(log n) time by finding the first and last positions of target with two binary searches, rather than scanning every element.
Test Case 1:
Input:nums = [1, 3, 5, 5, 5, 7, 9], target = 5
Output:3
Explanation:5 appears at indices 2, 3, and 4.
Test Case 2:
Input:nums = [1, 3, 5, 5, 5, 7, 9], target = 6
Output:0
Explanation:6 never appears in nums.
Test Case 3:
Input:nums = [1], target = 1
Output:1
Explanation:A single matching element.
Constraints
- ◆
1 ≤ nums.length ≤ 10⁴ - ◆
-10⁴ ≤ nums[i], target ≤ 10⁴ - ◆
nums is sorted in non-decreasing order (duplicates are allowed)
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public int countOccurrences(int[] nums, int target) { |
| 3 | int lo = 0, hi = nums.length - 1, first = -1; |
| 4 | while (lo <= hi) { |
| 5 | int mid = lo + (hi - lo) / 2; |
| 6 | if (nums[mid] >= target) { |
| 7 | first = mid; |
| 8 | hi = mid - 1; |
| 9 | } else { |
| 10 | lo = mid + 1; |
| 11 | } |
| 12 | } |
| 13 | if (first == -1 || nums[first] != target) { |
| 14 | return 0; |
| 15 | } |
| 16 | lo = 0; |
| 17 | hi = nums.length - 1; |
| 18 | int last = -1; |
| 19 | while (lo <= hi) { |
| 20 | int mid = lo + (hi - lo) / 2; |
| 21 | if (nums[mid] <= target) { |
| 22 | last = mid; |
| 23 | lo = mid + 1; |
| 24 | } else { |
| 25 | hi = mid - 1; |
| 26 | } |
| 27 | } |
| 28 | return last - first + 1; |
| 29 | } |
| 30 | } |
| 31 |
2
4
4
7
0
1
2
3
↑lo
↑hi
Variables
lo
0hi
3first
-1INITIALIZE
First, binary search [0, 3] for the leftmost index where nums[i] ≥ 4.
Step 1 / 8
Approach & Solutions
Brute Force — Linear Scan
BruteWalk the whole array once and count every position that matches target. Correct on any array, but it never uses the fact that equal values in a sorted array sit in one contiguous block, which is what lets binary search find the count in logarithmic time.
Time
O(n)Space
O(1)Java
1class Solution {
2 public int countOccurrences(int[] nums, int target) {
3 int count = 0;
4 for (int i = 0; i < nums.length; i++) {
5 if (nums[i] == target) count++;
6 }
7 return count;
8 }
9}Optimal — Two Binary Searches
OptimalEvery occurrence of target sits in one contiguous block, so the count is just (last index) - (first index) + 1. Binary-search once for the leftmost index with nums[i] ≥ target, and again for the rightmost index with nums[i] ≤ target.
Time
O(log n)Space
O(1)Java
1class Solution {
2 public int countOccurrences(int[] nums, int target) {
3 int lo = 0, hi = nums.length - 1, first = -1;
4 while (lo <= hi) {
5 int mid = lo + (hi - lo) / 2;
6 if (nums[mid] >= target) {
7 first = mid;
8 hi = mid - 1;
9 } else {
10 lo = mid + 1;
11 }
12 }
13 if (first == -1 || nums[first] != target) {
14 return 0;
15 }
16 lo = 0;
17 hi = nums.length - 1;
18 int last = -1;
19 while (lo <= hi) {
20 int mid = lo + (hi - lo) / 2;
21 if (nums[mid] <= target) {
22 last = mid;
23 lo = mid + 1;
24 } else {
25 hi = mid - 1;
26 }
27 }
28 return last - first + 1;
29 }
30}