Common Elements Present In All Rows Of Matrix

The idea is to iterate through the first row, and for each element of the row, iterate through all the other rows and check whether that element is present in them. If that element exists in all the other rows, we will add it to the output array. In the end, we will return the output array after removing duplicates.

Algorithm

• Iterate from k = 0 to M-1
  • If MAT[0][k] is already present in the output array, then we will ignore the current element and move ahead to the next element of the first array.
  • Define a flag isPresentInAllRows to store whether an element is present in all rows. Initialise it as 1.
  • Iterate from i = 1 to N-1
    • Define a flag variable isPresentInCurrentRow to check whether the element is present in the current row. Initialise it as 0.
    • Iterate from j = 0 to M-1 
      • If MAT[0][k] equals MAT[i][j] then set isPresentInCurrentRow to 1 and break the loop.
    • If isPresentInCurrent Row is equal to 0, then set isPresentInAllRows as 0 and break the loop.
  • If the flag variables isPresentInAllRows is set to 1, we will add MAT[0][k] to the output array.
• Return the output array.

The idea is to sort all the matrix rows and then maintain one pointer for each row. Let the array that stores the pointer to the column number currently being pointed for each row be currentColumn with all values initialised to 0. In each iteration, we first find the element which is currently pointed by the pointer to the first row, i.e., MAT[0][currentColumn[0]]. Then we move the pointers to all the other rows ahead while the element pointed by them is smaller than the element pointed in the first row. Then we check whether all the pointers are pointing to the same value. If yes, then we add that value to the output array provided it already does not exist in it and move the pointer to the first row ahead.

Algorithm

• Iterate from i = 0 to N - 1
  • Sort the i'th row of the matrix.
• Define an array currentColumn having N elements with all values currently initialised as 0.
• While currentColumn is less than M,
  • Let curr be mat[0][currentColumn[0]].
  • If mat[0][currentColumn[0]] is already present in the output array,  then we will ignore the current element and increase currentColumn[0] by 1 and move ahead without executing below ,statements. To check whether an element is already present in the output array, we just need to ensure that either the output array is empty or the last element of the output array is not equal to curr.
    • This idea works because adding an element that is not smaller than any of the output array element in each iteration. Therefore, we need to compare it with the largest element of the output array, i.e. its last element.
  • Define a flag variable isPresentInAllRows to determine whether the current element is present in all the rows. Initialise it as 1.
  • Iterate from i = 1 to N - 1 
    • While currentColumn[i]  is less than M and MAT[i][currentColumn[i]] is less than curr, 
      • Increase currentColumn[I] by 1.
    • If either currentColumn[i] becomes equal to ‘M’ or the value of MAT[i][currentColumn[i]] becomes greater than curr, then we will end this step here as we have already traversed one row entirely, and now we can not find any more new elements.
    • Otherwise if MAT[i][currentColumn[i]] is not equal to curr then set isPresentInAllRows as 0 and break the loop.
  • If the flag isPresentInAllRows equals,1 then we will add curr to the output array.
  • Increase currentColumn[0] by 1.
• Return the output array.

The idea is to use a HashMap to store the elements present in all the rows of the matrix. The advantage of using a HashMap is that it can search for an element present in the HashMap in constant time. Let commonElements be a HashMap having the matrix element as its key, and its corresponding value will be the maximum number of consecutive rows starting from the first row in which that element is present. We will first add all the first row elements in the HashMap and set their value as 1. Then we will traverse the matrix, and whenever we find an element that is present in all the previous rows, we will increase its corresponding value in the HashMap by 1 because that element was already present in the previous rows, and now we were able to find it in the current row. Therefore it is present in all the rows that have been traversed till now. In the end, we will iterate the commonElements HashMap and add all those keys to the output array whose corresponding value is equal to the number of rows of the matrix.

Algorithm

• Let commonElements be the HashMap that stores all the common Elements.
• Iterate from j = 0 to M - 1
  • Set commonElements[mat[0][j]] to 1.
• Iterate from i = 1 to N-1 
  • Iterate from j = 0 to M - 1
    • If MAT[i][j] is present in commonElements and commonElements[MAT[i][j]] equals i, then increase commonElements[MAT[i][j]] by 1. It means that the current element was present in all the previous rows of the matrix and now we were able to find it in the current row, therefore the maximum number of consecutive rows in which that element is present increases by 1.
• Iterate through the HashMap and add all keys having value N to the output array.
• Return the output array.