Given a sorted array of integers arr and a target value target, count the total number of times target appears in the array. If the target is not present, return 0.
Example 1
Input: arr = [1, 1, 2, 2, 2, 2, 3], target = 2
Output: 4
Explanation: The value 2 appears at indices 2, 3, 4, and 5, so the total count is 4.
Example 2
Input: arr = [1, 2, 3, 4, 5], target = 6
Output: 0
Explanation: The value 6 does not appear anywhere in the array.
Brute Force Approach
The most direct idea is to look at every element and count how many times the target appears. Nothing tricky is needed here. Every time the current value matches the target, the answer increases by 1. This works for any array, but it does not take advantage of the sorted order.
Algorithm
Start with a variable
count = 0because no occurrence has been seen yet.Traverse the array from left to right and check each element one by one.
If the current element is equal to the target, increase
countby1because one more valid occurrence has been found.Continue this process until the full array has been checked.
Return
countat the end because it stores the total number of matches.
Dry Run
Count Occurrence Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Counts how many times the target appears in the sorted array. */ int countOccurrence(vector<int>& arr, int target) { // Store the total number of matches found so far. int count = 0; // Check every element in the array. for (int i = 0; i < (int)arr.size(); i++) { // Increase the answer when the current value matches the target. if (arr[i] == target) { count++; } } return count; }};// Driver code startsint main() { vector<int> arr = {1, 1, 2, 2, 2, 2, 3}; int target = 2; Solution obj; cout << obj.countOccurrence(arr, target) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), N is the length of array, because every element may need to be checked once.
Space Complexity: O(1), because only a small fixed number of variables is used.
Optimal Approach
The useful observation is this: in a sorted array, all occurrences of the same value stay together in one continuous block. So instead of counting one by one, it is enough to find the first position where the target appears and the first position where values become greater than the target. The difference between these two positions gives the total number of occurrences. This is why lower bound and upper bound fit so nicely here.
Algorithm
Find the first index where the array value becomes greater than or equal to the target using binary search. This is the lower bound.
Find the first index where the array value becomes strictly greater than the target using binary search. This is the upper bound.
If the lower bound goes outside the array, or the value at that index is not equal to the target, return
0because the target is absent.Otherwise, subtract the lower bound from the upper bound.
Return that difference because it is exactly the size of the target block inside the sorted array.
Key Points
If the target does not exist, lower bound may point to another value or even to the array length.
The answer is
upperBound - lowerBound, notupperBound - lowerBound + 1, because upper bound points just after the last occurrence.
Dry Run
Count Occurrences Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Counts how many times the target appears in the sorted array. */ int countOccurrence(vector<int>& arr, int target) { // Find the first position where value is at least target. int first = lowerBound(arr, target); // If target is absent, there is nothing to count. if (first == (int)arr.size() || arr[first] != target) { return 0; } // Find the first position where value becomes greater than target. int afterLast = upperBound(arr, target); return afterLast - first; }private: int lowerBound(vector<int>& arr, int target) { int low = 0; int high = (int)arr.size() - 1; // Keep the best lower bound found so far. int answer = (int)arr.size(); while (low <= high) { int mid = low + (high - low) / 2; // This index can be a lower bound, so remember it and move left. if (arr[mid] >= target) { answer = mid; high = mid - 1; } else { // Current value is too small, so move to the right side. low = mid + 1; } } return answer; } int upperBound(vector<int>& arr, int target) { int low = 0; int high = (int)arr.size() - 1; // Keep the best upper bound found so far. int answer = (int)arr.size(); while (low <= high) { int mid = low + (high - low) / 2; // This index is greater than target, so it can be an upper bound. if (arr[mid] > target) { answer = mid; high = mid - 1; } else { // Current value still belongs to target or lies before it. low = mid + 1; } } return answer; }};// Driver code startsint main() { vector<int> arr = {1, 1, 2, 2, 2, 2, 3}; int target = 2; Solution obj; cout << obj.countOccurrence(arr, target) << endl; return 0;}Complexity Analysis
Time Complexity: O(log2 N), N is the length of array, because two binary searches are performed.
Space Complexity: O(1), because only a few variables are used.
Interview follow-up Questions
Because equal values stay together in one block. That makes it possible to find the starting and ending boundaries with binary search.
Be the first to add a comment.