sore_loser's blog

FInding maximum in matrix
By sore_loser, history, 9 years ago, In English

Suppose, I have a matrix with N rows and M columns. I want to find the number that appears most along with their frequencies for each row and each column. If there are multiple such numbers, any of them will do.

For example, let the matrix be a 4*3 matrix like this:

9 4 4

5 4 2

1 3 1

1 1 2

then I will perform calculation in these four arrays as follows:

rowval = {4,2,1,1} [ith value denotes the number that appears most in ith row]

rowfrq = {2,1,2,2} [the number of time the the max value of ith row appears]

colval = {1,4,2} [ith value denotes the number that appears most in ith column]

colfrq = {2,2,2} [the number of time the the max value of ith column appears]

What will be the most efficient way of performing this calculation? N*M can be upto 10^6 and the values of the matrix can be upto 10^6 as well . I was thinking of using map, but cannot understand what the complexity will be. Of course if there is a better approach, please help :)

  • Vote: I like it
  • -19
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

ongoing contest... Codechef february long challenge..

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

This is getting ridiculous. Almost every day some idiot (like you) asks about a problem from Codechef.

The big problem is that you ask about the simple ones. Please post questions about the hard ones :).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you for your help. There are some dimwits (like you) who can't resist commenting shit which is enough to show that I am on the right path.

    And following that path, I have just solved the problem :v Thanks again for your help, dimwit :v Should have not bothered commenting which would have prevented me digging deeper into this approach, dimwit. Take a lesson from here for the future and try not to show off everywhere, dimwit :v

    → Reply