Count Every Match, Not Just the First One

The count starts at zero and rises only when an element equals the target

To count occurrences, start count at 0 and traverse the array. For each index, compare arr[i] with target. Increase count only when the equality test is true. In the array [3, 7, 3, 2, 3, 7] with target = 3, the first element matches, so count changes from 0 to 1. The next element is 7, so count stays 1.

int count = 0;

for (int i = 0; i < n; i++) {
    if (arr[i] == target) {
        count++;
    }
}

The same rule continues through the rest of the array. The value at index 2 is 3, so count becomes 2. The value at index 3 is 2, so count stays 2. The value at index 4 is 3, so count becomes 3, and the final 7 at index 5 leaves it unchanged.

After each index, count equals the matches seen so far

You can predict count at any point by looking only at the elements tested so far. After index 0, one 3 has appeared, so count is 1. After index 1, it is still 1 because 7 is not the target. After index 2, it is 2. The value at index 3 does not match, index 4 adds another match, and index 5 does not change the result.

This gives count a precise meaning during the traversal: it is the number of occurrences of target among the indices processed so far. It is not yet the answer while untested elements remain, because one of those elements may still equal 3.

Finding the first 3 does not finish the count

A matching value tells you to increase the counter, not to stop the traversal. In this array, index 0 contains the target, but two more matching values are at indices 2 and 4. If you stop after the first match, you report 1 even though the target occurs 3 times.

int count = 0;

for (int i = 0; i < n; i++) {
    if (arr[i] == target) {
        count++;
        break;
    }
}

Without break, the loop continues to index 2 and increments count again, then reaches index 4 and increments it once more. The traversal must test every element because a later index can contain another occurrence even after an earlier match has been found.

if (arr[i] == target) {
    count++;
    break;
}

The count is final only after all six elements have been tested

For [3, 7, 3, 2, 3, 7], the complete trace is 0 before traversal, then 1, 1, 2, 2, 3, 3 after indices 0 through 5. The matching indices are 0, 2, and 4, so the final output is 3. The last value of count is trustworthy because every element has been compared with target.

A complete count makes n comparisons, one for each array element, so its time complexity is O(n). The algorithm stores only count and the loop index in addition to the existing array, so its extra space complexity is O(1).