C Program to find the first non-repeating element in an array

A non-repeating element is a value that occurs exactly once in an array. The first non-repeating element is the leftmost value whose total occurrence count is 1.

For example:

Array: 4 5 1 2 0 4 5 2

The first non-repeating element is 1. Although 0 also occurs once, 1 appears earlier in the array.

C Program to Find the First Non-Repeating Element

#include <stdio.h>

#define MAX_SIZE 100

int main(void) {
    int array[MAX_SIZE];
    int size;
    int firstNonRepeating = 0;
    int found = 0;

    printf("Enter the number of elements: ");
    if (scanf("%d", &size) != 1 || size < 1 || size > MAX_SIZE) {
        printf("Please enter a size between 1 and %d.\n", MAX_SIZE);
        return 1;
    }

    printf("Enter %d elements:\n", size);
    for (int index = 0; index < size; index++) {
        if (scanf("%d", &array[index]) != 1) {
            printf("Invalid array element.\n");
            return 1;
        }
    }

    for (int current = 0; current < size; current++) {
        int occurrenceCount = 0;

        for (int index = 0; index < size; index++) {
            if (array[current] == array[index]) {
                occurrenceCount++;
            }
        }

        if (occurrenceCount == 1) {
            firstNonRepeating = array[current];
            found = 1;
            break;
        }
    }

    if (found) {
        printf("First non-repeating element = %d\n", firstNonRepeating);
    } else {
        printf("The array has no non-repeating element.\n");
    }

    return 0;
}

Sample Output

Enter the number of elements: 8
Enter 8 elements:
4 5 1 2 0 4 5 2
First non-repeating element = 1

How the Program Works

1. The outer loop selects elements from left to right.
2. occurrenceCount is reset to 0 for each selected element.
3. The inner loop compares the selected value with every array element.
4. Each matching value increases occurrenceCount.
5. A count of exactly 1 means the selected element does not repeat.
6. The program saves that value and uses break because the first qualifying element has been found.
7. If no element has a count of 1, found remains 0.

Here is a shortened dry run:

Selected element	Occurrence count	Non-repeating?	Action
4	2	No	Continue
5	2	No	Continue
1	1	Yes	Save 1 and stop

The elements after 1 do not need to be selected because the program has already found the leftmost non-repeating value.

Why Count Across the Complete Array?

An element may appear only once in the portion examined so far but repeat later. For example, the first 4 in the sample initially looks unique, but another 4 appears near the end.

The inner loop checks the complete array before deciding whether the current value is non-repeating.

What If Every Element Repeats?

If every value occurs at least twice, the program does not find a count of 1:

Enter the number of elements: 6
Enter 6 elements:
3 7 3 9 7 9
The array has no non-repeating element.

What About a One-Element Array?

The only value in a one-element array occurs exactly once, so it is automatically the first non-repeating element.

Array: 42
First non-repeating element: 42

Does It Work with Negative Numbers and Zero?

Yes. The program compares integer values directly, so negative values and zero require no special handling. For -2, 0, -2, 5, the first non-repeating element is 0.

First Non-Repeating Element Versus All Unique Elements

Both problems look for values whose frequency is exactly 1, but their outputs differ:

• Find all unique elements: Continue through the entire array and print every value with a count of 1.
• Find the first non-repeating element: Stop after the first value with a count of 1.

For 4, 5, 1, 2, 0, 4, 5, 2, all unique elements are 1 and 0, while the first non-repeating element is only 1.

Alternative Approaches

When values lie within a small, known range, a frequency array can count all occurrences in O(n) time. A second left-to-right pass then finds the first value with frequency 1.

However, using input values directly as indices is unsafe for negative or out-of-range integers. The nested-loop method accepts any int, preserves the original order, and uses no auxiliary collection.

Sorting can group equal values but changes their order, so it cannot identify the original first non-repeating element unless original indices are stored separately.

Time and Space Complexity

• Best-case time complexity: O(n) because even the first candidate must be compared with every element to prove that it occurs once.
• Worst-case time complexity: O(n²) when many candidates repeat or no non-repeating element exists.
• Extra space complexity: O(1) because the search uses only counters, loop variables, a result variable, and a flag.

Common Mistakes

• Declaring an element non-repeating before checking the complete array.
• Printing every unique element instead of stopping after the first one.
• Forgetting to reset occurrenceCount for each candidate.
• Breaking the inner loop after the first match; every element matches itself once, so the complete frequency is required.
• Sorting the array and losing the original order.
• Using 0 as a not-found marker even though zero can be a valid array element; use a separate flag.

By checking candidate elements from left to right and stopping at the first value with a total frequency of one, the program finds the first non-repeating element without changing the array.