Finding the smallest common element in all rows of a matrix involves identifying an element that appears in every row and is the smallest among such elements. Here’s how you can approach this problem in C#.
Problem Statement
Given a 2D matrix (or list of lists), find the smallest element that is present in every row.
C# Implementation
Here’s a simple implementation to find the smallest common element:
using System;
using System.Collections.Generic;
public class SmallestCommonElementFinder
{
public static int? FindSmallestCommonElement(int[][] matrix)
{
if (matrix == null || matrix.Length == 0) return null;
// A dictionary to count occurrences of each element
Dictionary<int, int> countMap = new Dictionary<int, int>();
int rowCount = matrix.Length;
// Count occurrences of each element across all rows
foreach (var row in matrix)
{
HashSet<int> rowSet = new HashSet<int>();
foreach (var num in row)
{
// To avoid counting duplicates in the same row
if (rowSet.Add(num))
{
if (countMap.ContainsKey(num))
{
countMap[num]++;
}
else
{
countMap[num] = 1;
}
}
}
}
// Find the smallest element that appears in all rows
int? smallestCommonElement = null;
foreach (var kvp in countMap)
{
if (kvp.Value == rowCount) // Appears in all rows
{
if (smallestCommonElement == null || kvp.Key < smallestCommonElement)
{
smallestCommonElement = kvp.Key;
}
}
}
return smallestCommonElement; // Returns null if no common element found
}
public static void Main(string[] args)
{
int[][] matrix = new int[][]
{
new int[] { 1, 2, 3, 4 },
new int[] { 2, 3, 5, 6 },
new int[] { 1, 2, 3, 7 },
new int[] { 2, 8, 9, 3 }
};
int? result = FindSmallestCommonElement(matrix);
if (result.HasValue)
{
Console.WriteLine($"The smallest common element is: {result.Value}");
}
else
{
Console.WriteLine("No common element found.");
}
}
}
Explanation
-
Matrix Structure:
- The matrix is represented as a 2D array (
int[][]
), where each inner array corresponds to a row in the matrix.
- The matrix is represented as a 2D array (
-
FindSmallestCommonElement Method:
- This method takes the matrix as input and returns the smallest common element, or
null
if there isn’t one.
- This method takes the matrix as input and returns the smallest common element, or
-
Counting Occurrences:
- A
Dictionary<int, int>
(countMap
) is used to keep track of how many rows each element appears in. - For each row, a
HashSet<int>
(rowSet
) is utilized to ensure that we only count unique elements from that row.
- A
-
Populating the Dictionary:
- As we iterate through each element of the row, if it’s not already in
rowSet
, we add it and update its count incountMap
.
- As we iterate through each element of the row, if it’s not already in
-
Finding the Smallest Common Element:
- After counting, we iterate over the
countMap
to find the smallest key that has a count equal to the number of rows (rowCount
). - If found, this is our smallest common element.
- After counting, we iterate over the
-
Return Value:
- The method returns the smallest common element if it exists; otherwise, it returns
null
.
- The method returns the smallest common element if it exists; otherwise, it returns
-
Main Method:
- In the
Main
method, we create a sample matrix, call theFindSmallestCommonElement
method, and print the result.
- In the
Usage
You can modify the matrix
variable in the Main
method to test different configurations. This implementation efficiently finds the smallest common element that appears in all rows of the matrix.