BL
U

32. Check If Array Is Sorted in Nondecreasing Order

Easy

Problem Description

Determine whether an array of NN integers is sorted in non-decreasing order (A[i]≤A[i+1]A[i] \le A[i+1]). If sorted, print true. If not sorted, print false on line 1, and on line 2 print the first 0-based index ii where A[i]>A[i+1]A[i] > A[i+1].

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers A0,…,AN−1A_0, \dots, A_{N-1}.

Output Format

  • •Line 1: true or false
  • •Line 2 (if false): First index ii where A[i]>A[i+1]A[i] > A[i+1].
Example 1:
Input:
5
1 2 2 4 5
Output:
true
Explanation: Array is non-decreasing.
Example 2:
Input:
5
1 3 2 4 5
Output:
false
1
Explanation: Order breaks at index 1 because A[1] = 3 > A[2] = 2.
Example 3:
Input:
1
42
Output:
true
Explanation: Single element is trivially sorted.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online