package algoexpert.medium;

/*
PROBLEM:
Given matrix, find position of target
- rows & columns sorted
- height and width may not be equal

LOGIC:
t - target

c, c+1, c+2, .... , c + n
start with last col and find when c < t < c+1, go down in row

Solution:
1. time : O(m + n) | space : O(1)

*/

public class SearchSortedMatrix
{
    public static void test()
    {
        int[][] matrix = { {1,4,7,12,15,1000},
                           {2,5,19,31,32,1001},
                           {3,8,24,33,35,1002},
                           {40,41,42,44,45,1003},
                           {99,100,103,106,128,1004}
                         };
        int [] position = searchInSortedMatrix(matrix, 44);
        System.out.println("row : " + position[0]);
        System.out.println("col : " + position[1]);

    }

    public static int[] searchInSortedMatrix(int[][] matrix, int target) {
        int col = matrix[0].length - 1;
        int row = 0;

        while (row < matrix.length && col > -1)
        {
            if (target < matrix[row][col])
            { col -= 1; }
            else if (target > matrix[row][col])
            { row += 1; }
            else
            { return new int[] {row, col}; }
        }

        return new int[] {-1, -1};
    }
}