Tag time complexity

First Repeating Element in an Array: A Comprehensive Tutorial

Finding the first repeating element in an array is a classic algorithmic problem that tests understanding of arrays, hash tables, and time-space trade-offs. The goal is to identify the element that appears more than once and whose first occurrence (or second occurrence) comes earliest in the array.

This tutorial provides an in-depth exploration of finding the first repeating element in C: problem understanding, multiple approaches with different time/space complexities, implementation, edge cases, and best practices.

Conceptual Introduction & Fundamentals

What is a Repeating Element?

A repeating element is a value that appears more than once in an array. The “first repeating element” can be defined in two ways:

1. First by first occurrence: The element whose first occurrence has the smallest index among all repeating elements.
2. First by second occurrence: The element whose second occurrence has the smallest index (the first element to repeat as we scan left to right).

Example:

text

Array: [10, 5, 3, 4, 3, 5, 6] Repeating elements: 5 (appears twice), 3 (appears twice) First repeating element (by first occurrence): 5 (first occurs at index 1) First repeating element (by second occurrence): 3 (second occurrence at index 4, earlier than 5's second occurrence at index 5)

Problem Statement

Given an array of integers, find the first repeating element. Return the element value and/or its index. If no element repeats, indicate that.

Why This Problem Matters

• Algorithm design: Demonstrates brute force vs. optimized approaches.
• Hash table usage: Teaches efficient frequency counting.
• Time-space trade-offs: O(n²) time vs. O(n) time with O(n) space.
• Interview preparation: Common coding interview question.
• Data analysis: Finding duplicates in datasets.

Approaches Overview

Syntax & Core Mechanics

Approach 1: Brute Force (Nested Loops)

Check each element against all following elements to find duplicates.

c

#include <stdio.h> #include <stdbool.h> int findFirstRepeatingBrute(const int arr[], int n, int *element, int *index) { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { *element = arr[i]; *index = i; return 0; /* Found */ } } } return -1; /* Not found */ } int main(void) { int arr[] = {10, 5, 3, 4, 3, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int element, index; if (findFirstRepeatingBrute(arr, n, &element, &index) == 0) { printf("First repeating element: %d at index %d\n", element, index); } else { printf("No repeating element found.\n"); } return 0; }

Expected output:

text

First repeating element: 5 at index 1

Time complexity: O(n²)

Approach 2: Hash Table (Frequency Count)

Use a hash table or array to count frequencies, then find the first element with count > 1.

c

#include <stdio.h> #include <stdlib.h> #include <limits.h> /* Hash table entry */ typedef struct { int key; int count; int firstIndex; } HashEntry; /* Simple hash table */ typedef struct { HashEntry *entries; int size; int capacity; } HashTable; /* Hash function */ int hashFunction(int key, int capacity) { return (key % capacity + capacity) % capacity; /* Handle negative keys */ } /* Initialize hash table */ HashTable *createHashTable(int capacity) { HashTable *ht = malloc(sizeof(HashTable)); if (ht == NULL) return NULL; ht->entries = malloc(capacity * sizeof(HashEntry)); if (ht->entries == NULL) { free(ht); return NULL; } ht->size = 0; ht->capacity = capacity; /* Initialize entries */ for (int i = 0; i < capacity; i++) { ht->entries[i].key = INT_MIN; /* Sentinel for empty */ ht->entries[i].count = 0; ht->entries[i].firstIndex = -1; } return ht; } /* Insert or update key in hash table */ void hashTableInsert(HashTable *ht, int key, int index) { int hash = hashFunction(key, ht->capacity); int i = hash; /* Linear probing */ while (ht->entries[i].key != INT_MIN && ht->entries[i].key != key) { i = (i + 1) % ht->capacity; if (i == hash) return; /* Table full */ } if (ht->entries[i].key == INT_MIN) { ht->entries[i].key = key; ht->entries[i].count = 1; ht->entries[i].firstIndex = index; ht->size++; } else { ht->entries[i].count++; } } /* Get count for a key */ int hashTableGetCount(const HashTable *ht, int key) { int hash = hashFunction(key, ht->capacity); int i = hash; while (ht->entries[i].key != INT_MIN) { if (ht->entries[i].key == key) { return ht->entries[i].count; } i = (i + 1) % ht->capacity; if (i == hash) break; } return 0; } /* Get first index for a key */ int hashTableGetFirstIndex(const HashTable *ht, int key) { int hash = hashFunction(key, ht->capacity); int i = hash; while (ht->entries[i].key != INT_MIN) { if (ht->entries[i].key == key) { return ht->entries[i].firstIndex; } i = (i + 1) % ht->capacity; if (i == hash) break; } return -1; } /* Free hash table */ void freeHashTable(HashTable *ht) { if (ht != NULL) { free(ht->entries); free(ht); } } /* Find first repeating element using hash table */ int findFirstRepeatingHash(const int arr[], int n, int *element, int *index) { HashTable *ht = createHashTable(n * 2); if (ht == NULL) return -1; /* Insert all elements */ for (int i = 0; i < n; i++) { hashTableInsert(ht, arr[i], i); } /* Find first element with count > 1 */ for (int i = 0; i < n; i++) { if (hashTableGetCount(ht, arr[i]) > 1) { *element = arr[i]; *index = i; freeHashTable(ht); return 0; } } freeHashTable(ht); return -1; } int main(void) { int arr[] = {10, 5, 3, 4, 3, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int element, index; if (findFirstRepeatingHash(arr, n, &element, &index) == 0) { printf("First repeating element: %d at index %d\n", element, index); } else { printf("No repeating element found.\n"); } return 0; }

Expected output:

text

First repeating element: 5 at index 1

Time complexity: O(n), Space complexity: O(n)

Approach 3: Index Marking (For Constrained Arrays)

If array elements are between 0 and n-1, use index marking to find duplicates in O(n) time and O(1) space.

c

#include <stdio.h> #include <stdlib.h> /* Works only if all elements are in range [0, n-1] */ int findFirstRepeatingIndexMarking(int arr[], int n, int *element) { for (int i = 0; i < n; i++) { int absVal = abs(arr[i]); if (arr[absVal] < 0) { /* Already marked: this is a repeating element */ *element = absVal; return 0; } /* Mark as negative */ arr[absVal] = -arr[absVal]; } return -1; } int main(void) { int arr[] = {1, 2, 3, 1, 4, 2}; int n = sizeof(arr) / sizeof(arr[0]); int element; if (findFirstRepeatingIndexMarking(arr, n, &element) == 0) { printf("First repeating element: %d\n", element); } else { printf("No repeating element found.\n"); } return 0; }

Expected output:

text

First repeating element: 1

Note: This modifies the original array and only works for non-negative elements in range [0, n-1].

Full Practical Code Example with Explanation

This program demonstrates multiple approaches to find the first repeating element in an array, with performance comparison.

Program: First Repeating Element Finder

c

/** * first_repeating_element.c * Finds the first repeating element in an array using multiple approaches. * Compares brute force, hash table, and index marking methods. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #include <limits.h> #define MAX_LINE_LEN 100 #define MAX_ARRAY_SIZE 1000 /* Hash table for efficient frequency counting */ typedef struct { int key; int count; int firstIndex; int isOccupied; } HashSlot; typedef struct { HashSlot *slots; int capacity; } SimpleHashTable; /* Function prototypes */ int findFirstRepeatingBrute(const int arr[], int n, int *element, int *index); int findFirstRepeatingHash(const int arr[], int n, int *element, int *index); int findFirstRepeatingIndexMarking(int arr[], int n, int *element); SimpleHashTable *createHashTable(int capacity); void hashInsert(SimpleHashTable *ht, int key, int index); int hashGetCount(SimpleHashTable *ht, int key); void freeHashTable(SimpleHashTable *ht); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void demonstrateApproach(const char *name, int result, clock_t start, clock_t end); int main(void) { int choice; char buffer[MAX_LINE_LEN]; /* Test arrays */ int arr1[] = {10, 5, 3, 4, 3, 5, 6}; int n1 = sizeof(arr1) / sizeof(arr1[0]); int arr2[] = {1, 2, 3, 4, 5}; int n2 = sizeof(arr2) / sizeof(arr2[0]); int arr3[] = {1, 1, 1, 1}; int n3 = sizeof(arr3) / sizeof(arr3[0]); int arr4[] = {}; int n4 = 0; int arr5[] = {5}; int n5 = sizeof(arr5) / sizeof(arr5[0]); printf("=== First Repeating Element Finder ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate with Sample Arrays\n"); printf("2. Enter Custom Array\n"); printf("3. Performance Comparison\n"); printf("4. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: { printf("\n=== Sample Arrays ===\n"); printf("\nArray 1: "); printArray(arr1, n1); int element, index; if (findFirstRepeatingHash(arr1, n1, &element, &index) == 0) { printf("First repeating: %d at index %d\n", element, index); } else { printf("No repeating element.\n"); } printf("\nArray 2 (no repeats): "); printArray(arr2, n2); if (findFirstRepeatingHash(arr2, n2, &element, &index) == 0) { printf("First repeating: %d at index %d\n", element, index); } else { printf("No repeating element.\n"); } printf("\nArray 3 (all same): "); printArray(arr3, n3); if (findFirstRepeatingHash(arr3, n3, &element, &index) == 0) { printf("First repeating: %d at index %d\n", element, index); } else { printf("No repeating element.\n"); } printf("\nArray 4 (empty): "); printArray(arr4, n4); if (findFirstRepeatingHash(arr4, n4, &element, &index) == 0) { printf("First repeating: %d at index %d\n", element, index); } else { printf("No repeating element.\n"); } printf("\nArray 5 (single): "); printArray(arr5, n5); if (findFirstRepeatingHash(arr5, n5, &element, &index) == 0) { printf("First repeating: %d at index %d\n", element, index); } else { printf("No repeating element.\n"); } break; } case 2: { int n; if (readInteger("Enter array size (0-1000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 0 || n > MAX_ARRAY_SIZE) { printf("Size must be 0-%d.\n", MAX_ARRAY_SIZE); break; } int *customArr = malloc(n * sizeof(int)); if (customArr == NULL && n > 0) { fprintf(stderr, "Memory allocation failed.\n"); break; } printf("Enter %d elements:\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &customArr[i]) != 0) { fprintf(stderr, "Invalid element.\n"); free(customArr); break; } } printf("\nCustom array: "); printArray(customArr, n); int element, index; if (findFirstRepeatingHash(customArr, n, &element, &index) == 0) { printf("First repeating: %d at index %d\n", element, index); } else { printf("No repeating element.\n"); } free(customArr); break; } case 3: { printf("\n=== Performance Comparison ===\n"); int largeSize = 5000; int *largeArr = malloc(largeSize * sizeof(int)); if (largeArr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); break; } /* Fill with values, ensure some repeats */ srand(42); /* Fixed seed for reproducibility */ for (int i = 0; i < largeSize; i++) { largeArr[i] = rand() % 100; /* Values 0-99, many repeats */ } clock_t start, end; int element, index; /* Brute force */ start = clock(); int bruteResult = findFirstRepeatingBrute(largeArr, largeSize, &element, &index); end = clock(); demonstrateApproach("Brute force", bruteResult, start, end); /* Hash table */ start = clock(); int hashResult = findFirstRepeatingHash(largeArr, largeSize, &element, &index); end = clock(); demonstrateApproach("Hash table", hashResult, start, end); free(largeArr); break; } case 4: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Brute force: O(n^2) */ int findFirstRepeatingBrute(const int arr[], int n, int *element, int *index) { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) { *element = arr[i]; *index = i; return 0; } } } return -1; } /* Creates a hash table for frequency counting */ SimpleHashTable *createHashTable(int capacity) { SimpleHashTable *ht = malloc(sizeof(SimpleHashTable)); if (ht == NULL) return NULL; ht->slots = malloc(capacity * sizeof(HashSlot)); if (ht->slots == NULL) { free(ht); return NULL; } ht->capacity = capacity; for (int i = 0; i < capacity; i++) { ht->slots[i].key = 0; ht->slots[i].count = 0; ht->slots[i].firstIndex = -1; ht->slots[i].isOccupied = 0; } return ht; } /* Hash function with linear probing */ void hashInsert(SimpleHashTable *ht, int key, int index) { int hash = (key % ht->capacity + ht->capacity) % ht->capacity; int i = hash; while (ht->slots[i].isOccupied && ht->slots[i].key != key) { i = (i + 1) % ht->capacity; if (i == hash) return; /* Table full */ } if (!ht->slots[i].isOccupied) { ht->slots[i].key = key; ht->slots[i].count = 1; ht->slots[i].firstIndex = index; ht->slots[i].isOccupied = 1; } else { ht->slots[i].count++; } } /* Gets count for a key */ int hashGetCount(SimpleHashTable *ht, int key) { int hash = (key % ht->capacity + ht->capacity) % ht->capacity; int i = hash; while (ht->slots[i].isOccupied) { if (ht->slots[i].key == key) { return ht->slots[i].count; } i = (i + 1) % ht->capacity; if (i == hash) break; } return 0; } /* Frees hash table */ void freeHashTable(SimpleHashTable *ht) { if (ht != NULL) { free(ht->slots); free(ht); } } /* Hash table approach: O(n) time, O(n) space */ int findFirstRepeatingHash(const int arr[], int n, int *element, int *index) { SimpleHashTable *ht = createHashTable(n * 2 + 10); if (ht == NULL) return -1; for (int i = 0; i < n; i++) { hashInsert(ht, arr[i], i); } for (int i = 0; i < n; i++) { if (hashGetCount(ht, arr[i]) > 1) { *element = arr[i]; *index = i; freeHashTable(ht); return 0; } } freeHashTable(ht); return -1; } /* Index marking: O(n) time, O(1) space, modifies array */ int findFirstRepeatingIndexMarking(int arr[], int n, int *element) { for (int i = 0; i < n; i++) { int absVal = abs(arr[i]); if (arr[absVal] < 0) { *element = absVal; return 0; } arr[absVal] = -arr[absVal]; } return -1; } /* Displays approach result and time */ void demonstrateApproach(const char *name, int result, clock_t start, clock_t end) { double timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("%-20s: %s, Time = %.3f ms\n", name, result == 0 ? "Found" : "Not found", timeTaken); } /* Prints an array */ void printArray(const int arr[], int n) { if (n == 0) { printf("[]"); return; } printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]"); } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Approaches

1. Brute Force: Nested loops compare each element with all subsequent elements. O(n²).
2. Hash Table: Counts frequencies, then finds first element with count > 1. O(n) time, O(n) space.
3. Index Marking: Marks visited indices as negative; detects repeats. O(n) time, O(1) space, but modifies array.

Expected Output (sample run)

text

=== First Repeating Element Finder === --- Menu --- 1. Demonstrate with Sample Arrays 2. Enter Custom Array 3. Performance Comparison 4. Exit Enter choice: 1 === Sample Arrays === Array 1: [10, 5, 3, 4, 3, 5, 6] First repeating: 5 at index 1 Array 2 (no repeats): [1, 2, 3, 4, 5] No repeating element. Array 3 (all same): [1, 1, 1, 1] First repeating: 1 at index 0 Array 4 (empty): [] No repeating element. Array 5 (single): [5] No repeating element. --- Menu --- ... Enter choice: 3 === Performance Comparison === Brute force : Found, Time = 45.123 ms Hash table : Found, Time = 0.234 ms

Common Pitfalls, Edge Cases & Memory Considerations

1. Empty Array

Accessing arr[0] on an empty array is undefined behavior.

c

if (arr[0] == arr[1]) { // BUG: empty array }

Solution: Check n == 0 first.

2. Single Element Array

A single element cannot repeat. The function should return “not found.”

c

int arr[] = {5}; findFirstRepeating(arr, 1); // Should return -1

Solution: Ensure loop bounds handle n < 2 correctly.

3. Negative Numbers

Index marking approach fails with negative numbers because arr[absVal] may index out of bounds.

c

int arr[] = {-1, 2, -1}; // abs(-1) = 1, arr[1] is valid, but arr[-1] would be invalid

Solution: Use hash table approach for negative numbers, or offset values.

4. Elements Out of Range for Index Marking

Index marking requires all elements in [0, n-1]. Elements outside this range cause out-of-bounds access.

c

int arr[] = {100, 200, 100}; // arr[100] is out of bounds

Solution: Validate range before using index marking, or use hash table.

5. Large Element Values

Hash table with fixed-size array may not handle large element values without a proper hash function.

Solution: Use a proper hash table with collision handling, or use dynamic allocation.

6. All Elements Distinct

If no elements repeat, the function must correctly return “not found.”

c

int arr[] = {1, 2, 3, 4, 5}; findFirstRepeating(arr, 5); // Should return -1

Solution: Initialize result to -1 and only update when a repeat is found.

7. Memory Leaks in Hash Table

Forgetting to free the hash table causes memory leaks.

c

SimpleHashTable *ht = createHashTable(100); /* ... use ht ... */ /* Missing freeHashTable(ht); */

Solution: Always free dynamically allocated memory.

8. Integer Overflow in Hash Function

Large keys can overflow when computing hash.

c

int hash = key % capacity; // Overflow for very large key?

Solution: Use (key % capacity + capacity) % capacity to handle negatives safely.

9. Index Marking Modifies Original Array

Index marking changes the array by negating elements, making it unsuitable for read-only arrays.

Solution: Document that the function modifies the array, or create a copy.

10. Time-Space Trade-off

Brute force uses O(1) space but O(n²) time; hash table uses O(n) space but O(n) time. Choose based on constraints.

Solution: For small arrays, brute force is fine. For large arrays, use hash table.

Summary & Best Practices

Finding the first repeating element in an array is a classic problem that demonstrates the trade-off between time and space complexity. The hash table approach provides O(n) time, making it the preferred solution for large arrays.

Key Takeaways

• First repeating element can be defined by first occurrence or second occurrence.
• Brute force: O(n²) time, O(1) space.
• Hash table: O(n) time, O(n) space.
• Index marking: O(n) time, O(1) space (with constraints).
• Handle edge cases: empty array, single element, no repeats, all same.
• Choose approach based on array size and element range.

Best Practices

1. Use hash table approach for general cases with O(n) time.
2. Use brute force for very small arrays (n < 100) for simplicity.
3. Use index marking only when elements are in [0, n-1] and modification is acceptable.
4. Always check for empty arrays before processing.
5. Return a clear sentinel (e.g., -1) when no repeating element exists.
6. Free dynamically allocated memory in hash table approaches.
7. Document the approach’s constraints (e.g., modifies array, element range).
8. Test with diverse inputs: negatives, large values, duplicates at different positions.
9. Consider using built-in sorting if order doesn’t matter.
10. Profile performance for large arrays to choose the right algorithm.

By mastering this problem, you’ll understand fundamental algorithm design principles and be prepared for variations like finding all duplicates, first non-repeating element, and frequency counting.