Practice › Arrays
Check if Array is Sorted
Easy · Arrays · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Print YES if the array is sorted in non-decreasing order, otherwise NO.
Input
First line: n. Second line: n space-separated integers.
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a[i] ≤ 10^9
Example 1
Input
4 1 2 2 5
Output
YES
Example 2
Input
3 3 1 2
Output
NO
Hints
- A sorted array never has a[i] < a[i - 1].
- Equal neighbours are fine — the order is non-decreasing.
Approach
Compare every element with the previous one. The array is sorted unless some a[i] < a[i - 1]. An array with one element is always sorted.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
bool sorted = true;
for (int i = 1; i < n; i++)
if (a[i] < a[i - 1]) sorted = false;
cout << (sorted ? "YES" : "NO") << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1 : data[0] + 1]
print("YES" if all(a[i] >= a[i - 1] for i in range(1, n)) else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long prev = sc.nextLong();
boolean sorted = true;
for (int i = 1; i < n; i++) {
long x = sc.nextLong();
if (x < prev) sorted = false;
prev = x;
}
System.out.println(sorted ? "YES" : "NO");
}
}Solve Check if Array is Sorted online · All practice problems