Removing Duplicates in Go Using Nested Loops: A Comprehensive Guide

Table of Contents#

Understanding the Duplicate Removal Problem
Why Use Nested Loops?
Algorithm Design
Step-by-Step Implementation
Time Complexity Analysis
Testing and Example Usage
When to Avoid This Approach
Alternative Deduplication Methods
Best Practices & Common Pitfalls
Conclusion
References

1. Understanding the Duplicate Removal Problem#

Given a slice of elements (e.g., []int{2, 3, 2, 5, 7, 5}), the goal is to return a new slice containing only unique elements ([]int{2, 3, 5, 7}). Duplicates can appear anywhere in the collection, and order preservation is often desirable.

2. Why Use Nested Loops?#

Educational Value: Demonstrates fundamental loop mechanics and comparison logic.
No Memory Overhead: Avoids map allocations (useful in memory-constrained environments).
Order Preservation: Maintains original element sequence naturally.

Tradeoffs:

O(n²) time complexity (inefficient for large datasets).
Generally slower than map-based approaches for most real-world cases.

3. Algorithm Design#

Core Logic#

Iterate through each element (outer loop).
For each element, scan all prior elements (inner loop) to check for duplicates.
Only include the current element if no duplicate was found earlier in the slice.

Key Insight#

The inner loop checks indices 0 to i-1 for duplicates. If none are found, the element at i is unique so far.

4. Step-by-Step Implementation#

Complete Code#

package main
 
import "fmt"
 
func removeDuplicates(input []int) []int {
    result := []int{}
 
    for i := 0; i < len(input); i++ {
        duplicateFound := false
        // Check all elements BEFORE current index
        for j := 0; j < i; j++ {
            if input[i] == input[j] {
                duplicateFound = true
                break // Exit inner loop early
            }
        }
        // Append if no duplicate exists in prior elements
        if !duplicateFound {
            result = append(result, input[i])
        }
    }
    return result
}
 
func main() {
    data := []int{4, 2, 2, 8, 3, 3, 1, 4}
    unique := removeDuplicates(data)
    fmt.Printf("Original: %v\nDeduplicated: %v\n", data, unique)
}

Line-by-Line Explanation#

Initialize Result Slice: result starts empty.
Outer Loop (i): Processes every element in input.
Inner Loop (j): Checks elements from index 0 to i-1.
Duplicate Check: If input[i] matches any input[j], mark as duplicate.
Early Termination: break exits inner loop immediately upon finding a duplicate.
Append Unique Elements: Non-duplicates are added to result.

5. Time Complexity Analysis#

Worst-Case: O(n²)
Occurs when there are no duplicates (inner loop runs fully for every element).
Best-Case: O(n)
All elements are duplicates of the first element (inner loop breaks instantly).
Space Complexity: O(n)
Stores unique elements in a new slice.

6. Testing and Example Usage#

Sample Output#

Original: [4 2 2 8 3 3 1 4]
Deduplicated: [4 2 8 3 1]

Edge Case Tests#

Empty Slice: Returns [].
All Duplicates: []int{7, 7, 7} → []int{7}.
No Duplicates: Original slice returned unchanged.

7. When to Avoid This Approach#

Large Datasets: >1000 elements (performance degrades exponentially).
Time-Sensitive Operations: Use maps instead for O(n) complexity.
Unordered Data: If order preservation isn't required, maps are simpler.

8. Alternative Deduplication Methods#

Using Maps (Recommended for Most Cases)#

func dedupWithMap(input []int) []int {
    seen := make(map[int]struct{})
    result := []int{}
    for _, v := range input {
        if _, exists := seen[v]; !exists {
            seen[v] = struct{}{}
            result = append(result, v)
        }
    }
    return result
}

Advantages: O(n) time complexity, concise code.
Disadvantages: Doesn't preserve order. Go maps never guarantee iteration order; to preserve insertion order, maintain a separate slice of keys or use a third-party ordered map.

Sort-Based Approach#

Sort the slice first, then remove adjacent duplicates. Efficient but alters order.

9. Best Practices & Common Pitfalls#

Do#

Add bounds checks: if len(input) == 0 { return input }.
Use descriptive variable names (input/result vs arr/res).
Write unit tests for edge cases.

Avoid#

Modifying Input Slice: Always return a new slice.
Inner Loop Full-Scans: Only check indices j < i (not the entire slice).
Ignoring break: Exit early after finding a duplicate.

Performance Optimization#

For small slices with non-primitive types:

// Compare structs by field instead of entire value
if input[i].ID == input[j].ID { ... }

10. Conclusion#

Nested loops offer a straightforward way to remove duplicates while preserving order and avoiding extra memory usage. Although less efficient than map-based solutions for large datasets, this approach remains valuable for educational purposes and small-scale applications. Use the nested loop method when clarity and memory efficiency are priorities, but default to maps for production-grade deduplication at scale.