Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Example 1

Input

4
1 2 2 5

Output

YES

Example 2

Input

3
3 1 2

Output

NO

Hints

  1. A sorted array never has a[i] < a[i - 1].
  2. 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