Write a program to find duplicate elements count in a matrix

In this article, we will learn how to find the count of duplicate elements counts in a given matrix. This is an advanced version of finding the count of duplicate elements in a given array, though the logic we will apply to solve this problem will be similar.

Input

  • An input array.
  • Elements of array will be alpha numeric string

Output

  • Count of duplicates in a normal scenario and in case of exception return -1.

This question was recently asked in Goldman Sachs interview.

Approach

1. Brute Force Method

We can take an element an search in the complete matrix in given matrix. In this case, we should maintain the previously counted duplicate elements so that the previously counted duplicate element is not counted twice.

The time complexity of this approach will be O(n4), considering matrix of nxn

2. Using HashMap

In this approach, we will keep all elements of the matrix in a hashmap and count the number of occurrences. Once we have traversed all the elements of the matrix we can traverse hash map and count the elements which occurrence is greater than 1.

The time complexity of this approach will be O(n2) + O(n2) = O(n2)

Code Snippet

public class DuplicatesInMatrix {
	public static void main(String[] args) {
		String[][] arr = { { "1", "a", "1", "2" }, { "2", "b", "1", "e" },
				{ "3", "c", "d", "f" } };
		System.out
				.println("Duplicates in Given Matrix: " + findDuplicates(arr));
	}

	public static int findDuplicates(String[][] matrix) {
		HashMap<String, Integer> hm = new HashMap<>();
		int duplicateCount = 0;
		try {
			for (int i = 0; i < matrix.length; i++) {
				for (int j = 0; j < matrix[i].length; j++) {
					if (hm.containsKey(matrix[i][j])) {
						hm.put(matrix[i][j], hm.get(matrix[i][j]) + 1); //Optimization Line
					} else {
						hm.put(matrix[i][j], 1);
					}
				}
			}

			for (Entry<String, Integer> entry : hm.entrySet()) {
				if (entry.getValue() > 1) {
					duplicateCount++;
				}
			}
		} catch (Exception e) {
			return -1;
		}
		return duplicateCount;
	}
}

Output

Duplicates in Given Matrix: 2

Optimization

In the above approach, we have used to scans to matrix elements. We can solve this problem in only one scan if we update a variable duplicateCount on "optimization Line" marked in code. You can use condition as when ever the count becomes 2, update the duplicateCount. 

In this article, we learned to find the count of duplicate elements counts in a given matrix.

For more java programming questions 

 

For more data structure related programming questions 

Related Books

Book

Book

Java Book

Author
Author: Amit Gupta
Published On: 23/07/2017
Last revised On: 23/07/2017
View all articles by Amit Gupta

Share this post

Comments

Comments
comments powered by Disqus

Navigation

Social Media