0

I have a two dimensional array and I know:

  • The number of lines and the length of each line
  • Each line contains just positive numbers
  • Each line is sorted
  • not use with auxiliary array -not use with data structures

Required Output

I need to return the number which appears max times in the the whole array in an efficient way. I already tried to pass all over the array but it's not efficient.

This is an example of the array.

{
  {5, 7, 8},
  {6, 6},
  {null},
  {5, 6, 8, 9}
}

The expected return value for this example is 6.

I would like to get the explanation or code in c++

Thanks

Community
  • 1
  • 1
yakirhe
  • 13
  • 2

4 Answers4

0

For counting the number of times an element occurs in the array, a similar question using recursion is shown here.

Since you mentioned efficiency, it would help to sort the array in increasing or decreasing order prior to counting the number of times an element is present in the array (if unsorted). Although for a small input size as shown in your example, it wouldn't make much of a difference.

Community
  • 1
  • 1
HumanTorch
  • 349
  • 2
  • 5
  • 16
0

You could use map to keep track of the number of times its been repeated and a current max.

map<int, int> temp;
int currentMax= -999999,maxCount=0;
for(i=0; i< numberOflines ;i++)
{
        for(j=0;j< array[i].length;j++)
        {
            int newCount = ++temp[array[i][j]];
            if (maxCount < newCount) {
                 maxCount = newCount;
                 currentMax = array[i][j];
            }
        }
}
wrangler
  • 3,454
  • 1
  • 19
  • 28
0

Since a C/C++ solution is required then a 2D Array can be used. All the missing values can be represented by -1 (or any number which is not expected in valid numbers involved in search). So a empty row can be represented by all -1. See the code below. Since in C/C++, 2D array is continuously represented in memory. So we can convert 2D array to 1D array. Now we can sort the array. After sorting, all the '-1' will be at the beginning which can be discarded. From the leftover elements we can find the max frequency of an element.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main()
{
    int i, prev, max = -1, count = 0, maxvalue = -1;
    int a[4][4] = {{5, 7, 8, -1}, {6, 6, -1, -1}, {-1, -1, -1, -1}, {5, 6, 8, 9}};
    //int a[4][4] = {{-1, -1, -1, -1}, {-1, -1, -1, -1}, {-1, -1, -1, -1}, {-1, -1, -1, -1}};

    int *b = (int*)a;
    int total = sizeof(a) / sizeof(int);

    qsort(b, total, sizeof(int), compare);

    for(i = 0; i < total; ++i)
    {
            if(b[i] != -1)
            {
                    break;
            }
    }

    //printf("\n");

    i = i + 1;

    prev = -1;
    count = 0;
    if(i < total)
    {
            prev = b[i];
            count = 1;
    }
    for(i = i + 1; i < total; ++i)
    {
            //printf("prev=%d, b[i]=%d, max=%d, count=%d\n", prev, b[i], max, count);

            if(prev == b[i])
            {
                    count++;;
            }
            else
            {
                    if(max < count)
                    {
                            max = count;
                            maxvalue = prev;
                    }
                    prev = b[i];
                    count = 1;
            }
    }

    if(max != -1)
    {
            printf("Max Occurence of %d = %d\n", maxvalue, max);
    }
    else
    {
            printf("All the rows are of zero length\n");
    }

    return 0;
}
//Output:
Max Occurence of 6 = 3
sameerkn
  • 2,209
  • 1
  • 12
  • 13
  • This depends upon C++ allocating subarrays linearly, which it is under no obligation to do. In the event that it does not the result of this code will be undefined. – Jonathan Mee Jun 25 '16 at 20:54
  • @JonathanMee: Since the input is given as a 2D array, say A, therefore every element will be represent by `A[i][j]`. Now irrespective of how the data is stored in memory, we can access the elements of this 2D array in 1D manner as follows: `B[i*rows+j]`. This is because, there has to be some `function(A,i,j)` which can give access to element stored at A[i][j] irrespective of how the data is stored in memory. So instead of using `A[i][j]` we can use `function(A,i,j)` since both give access to same element. – sameerkn Jun 27 '16 at 05:58
  • "Now irrespective of how the data is stored in memory, we can access the elements of this 2D array in 1D manner as follows: B[i*rows+j]." **This is false.** Say for example the compiler decides to put `{5, 7, 8, -1}` @0x00001234 and `{6, 6, -1, -1}` @0x00001250, but then to avoid allocating a new page it puts `{-1, -1, -1, -1}` @0x00000012 and `{5, 6, 8, 9}` @0x00000028 now `a` contains: `{0x00001234, 0x00001250, 0x00000012, 0x00000028}` And when you try to access element `B[2 * 4 + 0]` you will be indexing out of bounds, making this code exhibit undefined behavior. – Jonathan Mee Jun 27 '16 at 10:49
  • @JonathanMee: Yes, I was little incorrect in saying that. What I finally meant was : there will be some `function(A, i, j)` which can provide access to elements which are arranged in 2D fashion. – sameerkn Jun 27 '16 at 11:59
  • Correct, but your code `int *b = (int*)a;` is an `reinterpret_cast` which will violate [the `reinterpret_cast`](http://en.cppreference.com/w/cpp/language/reinterpret_cast#Type_aliasing) contract when deference. Thus `qsort(b, total, sizeof(int), compare)` and every other access to `b` in this example is undefined behavior... **That makes this answer very bad and very misleading.** – Jonathan Mee Jun 27 '16 at 12:24
  • Welp. I am wrong about sub-arrays not being allocated linearly. [They are](http://stackoverflow.com/q/38057210/2642059) This code is still exhibits undefined behavior because of the `reinterpret_cast` violation. But not because of the sub-arrays. – Jonathan Mee Jun 27 '16 at 15:42
  • @JonathanMee: I do understand your concerns. For example if the 2D array is provided as `Lists of Lists` then in such case directly accessing element at `[i][j]` won't be possible. Since OP demanded code in C++, so is this technique will work as long as the array is allocated statically at compile time itself. If in C++ the 2D array is allocated dynamically then the example given by you `{0x00001234, 0x00001250, 0x00000012, 0x00000028}` holds and this code won't work. – sameerkn Jun 28 '16 at 06:18
  • `int *b = (int*)a` is not legal. In reality I believe the only concern there is appropriate write ordering, but the fact is the compiler is allowed to assume that you have not done something like that and optimize code accordingly. So while I would never use code like this I think in practice it will work. – Jonathan Mee Jun 28 '16 at 11:20
0

First off your input is illegal:

{
    {5, 7, 8},
    {6, 6},
    {null},
    {5, 6, 8, 9}
}

null is not defined by C++, and even if it was defined as 0 it would have to be interpreted as int(0), not an empty sub-array as I think that you intended.

I'm guessing that the input that you intend to imply should look something like this:

const initializer_list<int> a[] = {{5, 7, 8}, 
                                   {6, 6},
                                   {},
                                   {5, 6, 8, 9}};

You'll need to maintain a total for each number in any array. The best way to do that is to use map<int, int> totals which will only be constructed with the exact number of pairs as there are unique elements in a. The second element of each pair will be the count of that element seen thus far. You can populate it by doing:

for(const auto& i : a) for_each(cbegin(i), cend(i), [&](const auto& it){ totals[it]++;});

Once totals is populated you need only find its largest value:

cout << max_element(cbegin(totals), cend(totals), [](const auto& lhs, const auto& rhs){return lhs.second < rhs.second;})->first << endl;

Live Example

Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288