The bigger value in a matrix row

Question

How can I get the 2 biggers numbers of a matrix row?

If the matrix have a bigger number in other row, it can't be shown.

For example, let's suppose I have the following matrix

int mat[][] ={{1,2,3}{4,5,6}{7,8,9}};

if I search the 2 biggers numbers from the row 0, it should return me the indexes 1 and 2 (values 2 and 3).

Answer 1

Updated to return the indexes. Also, I imagine it's undesirable to change the original matrix in the course of this, so I wrote a test that confirmed my original implementation did change the matrix, then modified the code so it doesn't, anymore.

package playground.tests;

import java.util.Arrays;

import junit.framework.TestCase;

public class BiggerTest extends TestCase {

    public void testBigger() throws Exception {
        int mat[][] = { { 3, 1, 2 }, { 4, 5, 6 }, { 7, 8, 9 } };
        int[] result = bigger(0, 2, mat);
        assertEqualArrays(new int[] { 2, 3 }, result);
    }

    public void testBiggerDoesntChangeOriginalMatrix() throws Exception {
        int mat[][] = { { 3, 1, 2 }, { 4, 5, 6 }, { 7, 8, 9 } };
        bigger(0, 2, mat);
        assertEqualArrays(new int[] { 3, 1, 2 }, mat[0]);
    }

    public void testBiggerIndex() throws Exception {
        int mat[][] = { { 3, 1, 2 }, { 4, 5, 6 }, { 7, 8, 9 } };
        int[] result = biggerIndexes(0, 2, mat);
        assertEqualArrays(new int[] { 2, 0 }, result);
    }

    private int[] biggerIndexes(int rowIndex, int count, int[][] matrix) {
        int[] biggerValues = bigger(rowIndex, count, matrix);
        int[] row = matrix[rowIndex];
        int[] result = new int[count];
        for (int i = 0; i < result.length; i++) 
            result[i] = findIndex(biggerValues[i], row);
        return result;
    }

    private int findIndex(int value, int[] values) {
        for (int i = 0; i < values.length; i++) 
            if (values[i] == value)
                return i;
        return -1;
    }

    private int[] bigger(int rowIndex, int count, int[][] matrix) {
        int[] row = copy(matrix[rowIndex]);
        Arrays.sort(row);
        int[] result = new int[count];
        for (int i = 0; i < count; i++)
            result[i] = row[i + row.length - count];
        return result;
    }

    private static int[] copy(int[] original) {
        int[] result = new int[original.length];
        for (int i = 0; i < result.length; i++) 
            result[i] = original[i];
        return result;
    }

    private static void assertEqualArrays(int[] a, int[] b) {
        assertEquals(a.length, b.length);
        for (int i = 0; i < a.length; i++)
            assertEquals(a[i], b[i]);
    }
}

Answer 2

I made an adaption fro @Carl code, and I got this

private int[] bigger(int rowIndex, int count, int[][] matrix) {
    int[] row = matrix[rowIndex];
    int[] original = matrix[rowIndex];
    int[] result = new int[count];

    Arrays.sort(row);

    for (int i = 0; i < count; i++){
        for(int j = 0; j < original.length; j++){
            if(row[row.length - 1 - i] == original[j]){
                result[i] = j;
                original[j] = Integer.MIN_VALUE;
                // break;
            }
        }
    }
    return result;
}

we can put a break instruction where I commented, but I don't know if it will improve the performance of the algorithm.

Answer 3

Due to the way your "matrix" is stored in Java as an array of arrays, the problem is reduced to simply finding the indices of the highest 2 elements (possibly of equal values) in an int[].

The solution therefore is quite simple:

public class Max2 { 
    static int[] max2(int... nums) {
        int high1v = Integer.MIN_VALUE;
        int high2v = Integer.MIN_VALUE;
        int high1i = -1;
        int high2i = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= high1v) {
                high2v = high1v;
                high2i = high1i;
                high1v = nums[i];
                high1i = i;
            } else if (nums[i] >= high2v) {
                high2v = nums[i];
                high2i = i;
            }
        }
        return new int[] { high1i, high2i };
    }
}

This uses a 1-pass O(N) linear scan of the array. The combination of Integer.MIN_VALUE and >= comparison make it all work nicely. high1i is the index of the first highest element, high2v is the value of the second highest element, etc.

static void print(int[] arr) {
    System.out.println(java.util.Arrays.toString(arr));
}
public static void main(String[] args) {
    int[][] matrix = {
        { 1,2,3 }, // [2, 1]
        { 6,5,4 }, // [0, 1]
        { 8,7,9 }, // [2, 0]
        { 0,0,0 }, // [2, 1]
    };

    // print the indices of the maximum 2 elements in each row
    for (int[] row : matrix) {
        print(max2(row));
    }

    print(max2(matrix[1]));
    // matrix[1] is the { 6, 5, 4 } row; prints "[0, 1]"

    print(max2(Integer.MIN_VALUE, Integer.MIN_VALUE));
    // works with varargs, and Integer.MIN_VALUE as real values
}