Write A Code To Find Non Repeating Elements In An Array In Java

Finding non-repeating elements in an array is a common task in programming, often encountered in data processing and algorithm challenges. These are elements that appear only once within the array.

In this article, you will learn how to identify and extract non-repeating elements from an array in Java using various approaches, understanding their trade-offs in terms of efficiency and simplicity.

Problem Statement

The problem requires identifying all elements within a given array that appear exactly once. For instance, if an array contains [1, 2, 3, 2, 1, 4], the non-repeating elements are 3 and 4. This task is fundamental in data cleaning, frequency analysis, and preparing data for further processing where uniqueness is critical.

Example

Consider the input array: [5, 8, 2, 5, 8, 1, 9]

The non-repeating elements in this array are 2, 1, and 9.

Background & Knowledge Prerequisites

To effectively understand the solutions, readers should have a basic understanding of:

• Java Fundamentals: Variables, data types, control flow (loops, conditionals).
• Arrays: How to declare, initialize, and iterate through arrays.
• Collections Framework: Basic concepts of HashMap and potentially HashSet or ArrayList.

For the code examples, no special imports or setup are needed beyond standard Java Development Kit (JDK) installations.

Use Cases or Case Studies

Identifying non-repeating elements is useful in various scenarios:

• Data Deduplication: In datasets, finding values that appear only once can indicate unique identifiers or rare events.
• Log Analysis: Identifying unique error codes or user activities that occurred only once during a specific period can pinpoint isolated issues or unusual behavior.
• Game Development: Tracking unique items collected by a player or unique events triggered in a game.
• Voting Systems: In a simple voting system where each unique vote counts once, identifying unique voters or unique ballot choices.
• Interview Questions: A frequently asked algorithm question to test understanding of data structures and time complexity.

Solution Approaches

We will explore three distinct approaches to find non-repeating elements, ranging from a straightforward brute-force method to more optimized solutions using Java's Collections Framework.

Approach 1: Brute-Force (Nested Loops)

This approach involves comparing each element with every other element in the array to determine if it has any duplicates.

• One-line summary: Iterate through the array with nested loops; for each element, check if it has any other occurrences.

// NonRepeatingElementsBruteForce
public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 5, 8, 1, 9};

        System.out.println("Non-repeating elements (Brute-Force):");

        // Step 1: Iterate through each element in the array
        for (int i = 0; i < arr.length; i++) {
            boolean isRepeating = false;
            // Step 2: Compare the current element with all other elements
            for (int j = 0; j < arr.length; j++) {
                // Step 3: Skip self-comparison
                if (i != j && arr[i] == arr[j]) {
                    isRepeating = true;
                    break; // Found a repeat, no need to check further for this element
                }
            }
            // Step 4: If no repeat was found, it's a non-repeating element
            if (!isRepeating) {
                System.out.println(arr[i]);
            }
        }
    }
}

Run

• Sample output:

  Non-repeating elements (Brute-Force):
  2
  1
  9

• Stepwise explanation for clarity:

1. Initialize an integer array arr with example values.
2. Use an outer loop to pick each element one by one. Let's call the index i.
3. Inside the outer loop, initialize a boolean flag isRepeating to false. This flag will track if the current element arr[i] is found anywhere else.
4. Use an inner loop (index j) to iterate through the entire array again.
5. Inside the inner loop, check if i is not equal to j (to avoid comparing an element with itself) AND arr[i] is equal to arr[j].
6. If a match is found, set isRepeating to true and break from the inner loop, as we've confirmed it's a repeating element.
7. After the inner loop completes, if isRepeating is still false, it means arr[i] appeared only once, so print it.

Approach 2: Using HashMap (Frequency Counter)

This method is more efficient, especially for larger arrays. It leverages a HashMap to store the frequency of each element.

• One-line summary: Use a HashMap to count occurrences of each element, then iterate the map or array to find elements with a count of 1.

// NonRepeatingElementsHashMap
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 5, 8, 1, 9};

        System.out.println("Non-repeating elements (HashMap):");

        // Step 1: Create a HashMap to store element frequencies
        Map<Integer, Integer> frequencyMap = new HashMap<>();

        // Step 2: Iterate through the array and populate the frequency map
        for (int element : arr) {
            frequencyMap.put(element, frequencyMap.getOrDefault(element, 0) + 1);
        }

        // Step 3: Iterate through the array again to maintain original order
        //         and print elements with a frequency of 1
        for (int element : arr) {
            if (frequencyMap.get(element) == 1) {
                System.out.println(element);
            }
        }
        
        // Alternative Step 3: Iterate through the map (order not guaranteed)
        // for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
        //     if (entry.getValue() == 1) {
        //         System.out.println(entry.getKey());
        //     }
        // }
    }
}

Run

• Sample output:

  Non-repeating elements (HashMap):
  2
  1
  9

• Stepwise explanation for clarity:

1. Initialize an integer array arr.
2. Create an empty HashMap named frequencyMap. This map will store each unique array element as a key and its count as the value.
3. Iterate through the arr array using an enhanced for-loop.
4. For each element, update its count in the frequencyMap. frequencyMap.getOrDefault(element, 0) retrieves the current count (or 0 if not present), and + 1 increments it.
5. After populating the map, iterate through the *original array* arr again. This is important to print the non-repeating elements in their order of first appearance if that's a requirement.
6. For each element in the array, check its frequency in the frequencyMap. If frequencyMap.get(element) is 1, it means the element appeared only once, so print it.

Approach 3: Using a Frequency Array (for limited range integers)

If the array elements are integers within a known, relatively small non-negative range (e.g., 0 to 1000), a simple array can be used as a frequency counter, offering even better performance than a HashMap due to direct indexing.

• One-line summary: Use an auxiliary array as a direct lookup table to store counts of elements if their range is constrained.

// NonRepeatingElementsFrequencyArray
public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 5, 8, 1, 9};
        // Assuming elements are within 0-10 (adjust MAX_VALUE as needed)
        final int MAX_VALUE = 10; 

        System.out.println("Non-repeating elements (Frequency Array):");

        // Step 1: Create a frequency array, initialized to zeros
        // The size should be MAX_VALUE + 1 to accommodate MAX_VALUE itself
        int[] frequencyArray = new int[MAX_VALUE + 1];

        // Step 2: Iterate through the input array and populate the frequency array
        for (int element : arr) {
            // Ensure element is within bounds
            if (element >= 0 && element <= MAX_VALUE) {
                frequencyArray[element]++;
            } else {
                System.out.println("Warning: Element " + element + " out of assumed range [0, " + MAX_VALUE + "]");
            }
        }

        // Step 3: Iterate through the original array to find elements with frequency 1
        //         (maintaining original order of first appearance)
        for (int element : arr) {
            if (element >= 0 && element <= MAX_VALUE && frequencyArray[element] == 1) {
                System.out.println(element);
                // Optional: Mark as processed if you only want to print once even if it appears multiple times as unique in the first loop
                // frequencyArray[element] = 0; 
            }
        }
    }
}

Run

• Sample output:

  Non-repeating elements (Frequency Array):
  2
  1
  9

• Stepwise explanation for clarity:

1. Initialize an integer array arr and define MAX_VALUE based on the expected maximum value in the array.
2. Create an auxiliary int array frequencyArray of size MAX_VALUE + 1. All elements will be initialized to 0 by default.
3. Iterate through the input arr. For each element, use it as an index into frequencyArray and increment the value at that index. This directly counts the occurrences.
4. After populating the frequencyArray, iterate through the *original array* arr again.
5. For each element in arr, check its count in frequencyArray[element]. If the count is 1, print the element as it is non-repeating.

Conclusion

We've explored different strategies for identifying non-repeating elements in a Java array. The brute-force approach is simple to understand but less efficient for large datasets. The HashMap-based solution provides a robust and efficient way to handle arbitrary integer ranges and is generally preferred for its balance of performance and flexibility. For specific cases where integer elements fall within a small, known non-negative range, a frequency array offers the best performance due to direct indexing. Choosing the right approach depends on the array's size, the range of its elements, and the performance requirements of your application.

Summary

• Problem: Find elements that appear exactly once in an array.
• Brute-Force: Uses nested loops, time complexity O(n^2), simple for small arrays.
• HashMap: Uses a frequency map (key=element, value=count), time complexity O(n) for two passes, efficient and flexible.
• Frequency Array: Uses an auxiliary array as a direct counter (index=element, value=count), time complexity O(n) for two passes, most efficient for small, constrained integer ranges.
• Choice of Method: HashMap is a good general-purpose choice; frequency array is an optimization for specific data ranges.