Find smallest common element in all rows problem in c#

Programming C#
1

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

  1. Matrix Structure:

    • The matrix is represented as a 2D array (int[][]), where each inner array corresponds to a row in the matrix.

  2. FindSmallestCommonElement Method:

    • This method takes the matrix as input and returns the smallest common element, or null if there isn’t one.

  3. 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.

  4. 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 in countMap.

  5. 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.

  6. Return Value:

    • The method returns the smallest common element if it exists; otherwise, it returns null.

  7. Main Method:

    • In the Main method, we create a sample matrix, call the FindSmallestCommonElement method, and print the result.

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.