First Sorted Row

Difficulty: ⚫⚫◯◯

Tags: array, 2d-array, searching, comparison

Hurdle: Passing this question is sufficient to pass the arrays hurdle.

Description

Write a function first_sorted_row that determines whether there is a row in a two-dimensional array whose elements are in strictly increasing order.

The function is given:

num_rows: the number of rows in the array
array: the two-dimensional array of integers, with NUM_COLS columns, where NUM_COLS is #defined to 5

A row is strictly increasing when every element is strictly greater than the element to its left. The function should return the index of the first such row, or -1 if no such row exists.

Note that "strictly greater" means equal neighbours are not allowed. The row [1, 2, 2, 3, 4] is not strictly increasing, because 2 is not strictly greater than 2.

Examples

Example 1

[10, 5, 8, 2,  1],
[ 1, 2, 3, 4,  5],
[ 2, 4, 6, 8, 10],
[ 5, 5, 5, 5,  5]

Output: 1

Explanation: Row 0 is not increasing, since 5 is not greater than 10. Row 1 is strictly increasing, so its index is returned. Row 2 is also strictly increasing, but row 1 comes first.

Example 2

[1, 2, 2, 3, 4],
[5, 4, 3, 2, 1],
[9, 8, 7, 6, 5]

Output: -1

Explanation: Row 0 fails because 2 is not strictly greater than 2, even though the rest of the row increases. Rows 1 and 2 are decreasing. No row qualifies, so the answer is -1.

Example 3

[10, 20, 30, 40, 50],
[ 1,  2,  3,  4,  5]

Output: 0

Explanation: The very first row is strictly increasing.

Example 4

[16, 12,  8,  4,  1],
[ 2,  4, 10, 15, 20],
[ 3,  6, 12, 11, 20],
[ 5,  5,  5,  5,  5]

Output: 1

Explanation: Row 0 decreases. Row 1 is strictly increasing. Row 2 would fail anyway, since 11 is not greater than 12.

Example 5

[5, 4, 3, 2, 9],
[1, 2, 3, 4, 5]

Output: 1

Explanation: Row 0 contains one increasing step, from 2 up to 9, but it is not strictly increasing overall. A single increasing pair is not enough.

Function Signature

int first_sorted_row(int num_rows, int array[][NUM_COLS]);

Constraints

first_sorted_row should return a single integer, either a row index or -1.
You may assume num_rows will always be at least 1.
The number of columns is fixed by the constant NUM_COLS.
Array elements may be negative.
Return the index of the first qualifying row if more than one qualifies.
first_sorted_row should not change the array it is given.
Do not call scanf, getchar, or fgets.
Do not call printf (the function should only return a value).

Hints

"Every element is greater than the one to its left" is an all condition, not an any condition. Returning as soon as you see one increasing pair is the most common way to get this wrong. Row [5, 4, 3, 2, 9] contains an increasing pair but is not sorted.
The usual way to handle an all condition is to assume the row qualifies, then look for a single counterexample that proves it does not.
Because of that, you only know the verdict for a row after the inner loop has finished. The check that decides whether to return must sit outside the inner loop, not inside it.
Anything that describes one row must be reset at the start of every row.
You are comparing each element with its left neighbour, so the loop body needs both array[row][col] and array[row][col - 1]. Start the inner loop at col = 1 so that col - 1 is always a valid index.
Do not forget the final return -1 for when no row qualifies.

Testing

Each command line argument is one row, written as 5 comma-separated values.

./first-sorted-row 10,5,8,2,1 1,2,3,4,5 2,4,6,8,10 5,5,5,5,5
1

./first-sorted-row 1,2,2,3,4 5,4,3,2,1 9,8,7,6,5
-1

./first-sorted-row 10,20,30,40,50 1,2,3,4,5
0

./first-sorted-row 5,5,5,5,5
-1

./first-sorted-row 1,2,3,4,4
-1

./first-sorted-row 2,1,3,4,5
-1

./first-sorted-row 5,4,3,2,9 1,2,3,4,5
1

./first-sorted-row 5,4,3,2,1 9,9,9,9,9 3,1,4,1,5 -3,-2,-1,0,1
3