Check if Array is Sorted

Determine if an array is sorted in ascending, descending, or not sorted at all

Language Selection

Choose your preferred programming language

Showing: Python

Check if Array is Sorted

Problem Statement

Given an array of integers, determine if the array is sorted in ascending order, descending order, or not sorted at all. Return the sorting status of the array.

Input/Output Specifications

Input: An array of integers nums where 0 <= nums.length <= 10^5 and -10^9 <= nums[i] <= 10^9
Output: A string indicating the sorting status: “ascending”, “descending”, or “not sorted”

Constraints

The array can be empty (considered sorted)
Array elements can be negative, positive, or zero
Arrays with duplicate consecutive elements are still considered sorted
Single element arrays are considered sorted in both directions

Examples

Example 1:

Input: nums = [1, 2, 3, 4, 5]
Output: "ascending"
Explanation: Each element is greater than or equal to the previous one.

Example 2:

Input: nums = [5, 4, 3, 2, 1]
Output: "descending"
Explanation: Each element is less than or equal to the previous one.

Example 3:

Input: nums = [1, 3, 2, 4]
Output: "not sorted"
Explanation: The array is neither ascending nor descending.

Example 4:

Input: nums = [1, 1, 1, 1]
Output: "ascending"
Explanation: All elements are equal, satisfies ascending condition.

Example 5:

Input: nums = []
Output: "ascending"
Explanation: Empty arrays are considered sorted.

Solution Approaches

Approach 1: Single Pass with Direction Detection (Optimal)

Algorithm Explanation:

Handle edge cases (empty array or single element)
Iterate through the array comparing adjacent elements
Track if we’ve seen any ascending or descending pairs
If we see both ascending and descending pairs, array is not sorted
Determine the final sorting direction based on observed patterns

Implementation:

Python:

def check_if_sorted(nums):
    """
    Check if array is sorted using single pass
    Time: O(n)
    Space: O(1)
    """
    if len(nums) <= 1:
        return "ascending"  # Empty or single element is considered ascending
    
    has_ascending = False
    has_descending = False
    
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            has_ascending = True
        elif nums[i] < nums[i-1]:
            has_descending = True
        
        # Early termination if both directions found
        if has_ascending and has_descending:
            return "not sorted"
    
    # Determine final state
    if has_ascending:
        return "ascending"
    else:
        return "descending"  # All equal or strictly descending

# Alternative boolean return version
def is_sorted_ascending(nums):
    """
    Check if array is sorted in ascending order
    Time: O(n)
    Space: O(1)
    """
    if len(nums) <= 1:
        return True
    
    for i in range(1, len(nums)):
        if nums[i] < nums[i-1]:
            return False
    
    return True

def is_sorted_descending(nums):
    """
    Check if array is sorted in descending order
    Time: O(n)
    Space: O(1)
    """
    if len(nums) <= 1:
        return True
    
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            return False
    
    return True

Java:

class Solution {
    /**
     * Check if array is sorted using single pass
     * Time: O(n)
     * Space: O(1)
     */
    public String checkIfSorted(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return "ascending";
        }
        
        boolean hasAscending = false;
        boolean hasDescending = false;
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i-1]) {
                hasAscending = true;
            } else if (nums[i] < nums[i-1]) {
                hasDescending = true;
            }
            
            // Early termination if both directions found
            if (hasAscending && hasDescending) {
                return "not sorted";
            }
        }
        
        return hasAscending ? "ascending" : "descending";
    }
    
    // Alternative boolean methods
    public boolean isSortedAscending(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return true;
        }
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i-1]) {
                return false;
            }
        }
        
        return true;
    }
    
    public boolean isSortedDescending(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return true;
        }
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i-1]) {
                return false;
            }
        }
        
        return true;
    }
}

Go:

// checkIfSorted - Check if array is sorted using single pass
// Time: O(n)
// Space: O(1)
func checkIfSorted(nums []int) string {
    if len(nums) <= 1 {
        return "ascending"
    }
    
    hasAscending := false
    hasDescending := false
    
    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] {
            hasAscending = true
        } else if nums[i] < nums[i-1] {
            hasDescending = true
        }
        
        // Early termination if both directions found
        if hasAscending && hasDescending {
            return "not sorted"
        }
    }
    
    if hasAscending {
        return "ascending"
    }
    return "descending"
}

// Alternative boolean functions
func isSortedAscending(nums []int) bool {
    if len(nums) <= 1 {
        return true
    }
    
    for i := 1; i < len(nums); i++ {
        if nums[i] < nums[i-1] {
            return false
        }
    }
    
    return true
}

func isSortedDescending(nums []int) bool {
    if len(nums) <= 1 {
        return true
    }
    
    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] {
            return false
        }
    }
    
    return true
}

JavaScript:

/**
 * Check if array is sorted using single pass
 * Time: O(n)
 * Space: O(1)
 */
function checkIfSorted(nums) {
    if (!nums || nums.length <= 1) {
        return "ascending";
    }
    
    let hasAscending = false;
    let hasDescending = false;
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i-1]) {
            hasAscending = true;
        } else if (nums[i] < nums[i-1]) {
            hasDescending = true;
        }
        
        // Early termination if both directions found
        if (hasAscending && hasDescending) {
            return "not sorted";
        }
    }
    
    return hasAscending ? "ascending" : "descending";
}

// Alternative boolean methods
function isSortedAscending(nums) {
    if (!nums || nums.length <= 1) {
        return true;
    }
    
    return nums.every((num, i) => i === 0 || num >= nums[i-1]);
}

function isSortedDescending(nums) {
    if (!nums || nums.length <= 1) {
        return true;
    }
    
    return nums.every((num, i) => i === 0 || num <= nums[i-1]);
}

// Using reduce for functional approach
function checkIfSortedReduce(nums) {
    if (!nums || nums.length <= 1) {
        return "ascending";
    }
    
    const result = nums.reduce((acc, curr, i) => {
        if (i === 0) return acc;
        
        if (curr > nums[i-1]) acc.hasAscending = true;
        else if (curr < nums[i-1]) acc.hasDescending = true;
        
        return acc;
    }, { hasAscending: false, hasDescending: false });
    
    if (result.hasAscending && result.hasDescending) {
        return "not sorted";
    }
    
    return result.hasAscending ? "ascending" : "descending";
}

C#:

public class Solution {
    /// <summary>
    /// Check if array is sorted using single pass
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public string CheckIfSorted(int[] nums) {
        if (nums == null || nums.Length <= 1) {
            return "ascending";
        }
        
        bool hasAscending = false;
        bool hasDescending = false;
        
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] > nums[i-1]) {
                hasAscending = true;
            } else if (nums[i] < nums[i-1]) {
                hasDescending = true;
            }
            
            // Early termination if both directions found
            if (hasAscending && hasDescending) {
                return "not sorted";
            }
        }
        
        return hasAscending ? "ascending" : "descending";
    }
    
    // Alternative boolean methods
    public bool IsSortedAscending(int[] nums) {
        if (nums == null || nums.Length <= 1) {
            return true;
        }
        
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] < nums[i-1]) {
                return false;
            }
        }
        
        return true;
    }
    
    // Using LINQ
    public string CheckIfSortedLinq(int[] nums) {
        if (nums == null || nums.Length <= 1) {
            return "ascending";
        }
        
        bool isAscending = nums.Zip(nums.Skip(1), (a, b) => a <= b).All(x => x);
        bool isDescending = nums.Zip(nums.Skip(1), (a, b) => a >= b).All(x => x);
        
        if (isAscending && !isDescending) return "ascending";
        if (isDescending && !isAscending) return "descending";
        if (isAscending && isDescending) return "ascending"; // All equal
        
        return "not sorted";
    }
}

Complexity Analysis:

Time Complexity: O(n) - We examine each adjacent pair once, with early termination
Space Complexity: O(1) - Only using a constant amount of extra space

Trade-offs:

Optimal time complexity with single pass
Early termination saves time when array is clearly unsorted
Simple boolean logic
Handles edge cases cleanly

Approach 2: Compare with Sorted Version

Algorithm Explanation:

Create sorted copies of the array (ascending and descending)
Compare the original array with both sorted versions
Return the matching direction or “not sorted”

Implementation:

Python:

def check_if_sorted_compare(nums):
    """
    Check if array is sorted by comparing with sorted versions
    Time: O(n log n)
    Space: O(n)
    """
    if len(nums) <= 1:
        return "ascending"
    
    ascending_sorted = sorted(nums)
    descending_sorted = sorted(nums, reverse=True)
    
    if nums == ascending_sorted:
        return "ascending"
    elif nums == descending_sorted:
        return "descending"
    else:
        return "not sorted"

Java:

class Solution {
    /**
     * Check if array is sorted by comparing with sorted versions
     * Time: O(n log n)
     * Space: O(n)
     */
    public String checkIfSortedCompare(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return "ascending";
        }
        
        int[] ascending = nums.clone();
        int[] descending = nums.clone();
        
        Arrays.sort(ascending);
        Arrays.sort(descending);
        
        // Reverse for descending
        for (int i = 0; i < descending.length / 2; i++) {
            int temp = descending[i];
            descending[i] = descending[descending.length - 1 - i];
            descending[descending.length - 1 - i] = temp;
        }
        
        if (Arrays.equals(nums, ascending)) {
            return "ascending";
        } else if (Arrays.equals(nums, descending)) {
            return "descending";
        } else {
            return "not sorted";
        }
    }
}

Go:

// checkIfSortedCompare - Check by comparing with sorted versions
// Time: O(n log n)
// Space: O(n)
func checkIfSortedCompare(nums []int) string {
    if len(nums) <= 1 {
        return "ascending"
    }
    
    // Create copies for sorting
    ascending := make([]int, len(nums))
    descending := make([]int, len(nums))
    copy(ascending, nums)
    copy(descending, nums)
    
    sort.Ints(ascending)
    sort.Sort(sort.Reverse(sort.IntSlice(descending)))
    
    // Compare arrays
    if reflect.DeepEqual(nums, ascending) {
        return "ascending"
    } else if reflect.DeepEqual(nums, descending) {
        return "descending"
    } else {
        return "not sorted"
    }
}

JavaScript:

/**
 * Check if array is sorted by comparing with sorted versions
 * Time: O(n log n)
 * Space: O(n)
 */
function checkIfSortedCompare(nums) {
    if (!nums || nums.length <= 1) {
        return "ascending";
    }
    
    const ascending = [...nums].sort((a, b) => a - b);
    const descending = [...nums].sort((a, b) => b - a);
    
    const arraysEqual = (a, b) => 
        a.length === b.length && a.every((val, i) => val === b[i]);
    
    if (arraysEqual(nums, ascending)) {
        return "ascending";
    } else if (arraysEqual(nums, descending)) {
        return "descending";
    } else {
        return "not sorted";
    }
}

C#:

public class Solution {
    /// <summary>
    /// Check if array is sorted by comparing with sorted versions
    /// Time: O(n log n)
    /// Space: O(n)
    /// </summary>
    public string CheckIfSortedCompare(int[] nums) {
        if (nums == null || nums.Length <= 1) {
            return "ascending";
        }
        
        int[] ascending = (int[])nums.Clone();
        int[] descending = (int[])nums.Clone();
        
        Array.Sort(ascending);
        Array.Sort(descending);
        Array.Reverse(descending);
        
        if (nums.SequenceEqual(ascending)) {
            return "ascending";
        } else if (nums.SequenceEqual(descending)) {
            return "descending";
        } else {
            return "not sorted";
        }
    }
}

Complexity Analysis:

Time Complexity: O(n log n) - Due to sorting operations
Space Complexity: O(n) - For creating sorted copies

Trade-offs:

Simpler logic but less efficient
Uses more memory
No early termination benefit
Good for when you need sorted arrays anyway

Key Insights

Single Pass Optimization: The optimal solution only needs one pass through the array
Early Termination: Can stop as soon as both ascending and descending patterns are detected
Edge Case Handling: Empty arrays and single elements need special consideration
Equal Elements: Arrays with all equal elements are considered sorted in ascending order

Edge Cases

Empty Array: [] → Returns "ascending"
Single Element: [5] → Returns "ascending"
All Equal: [3, 3, 3] → Returns "ascending"
Strictly Ascending: [1, 2, 3] → Returns "ascending"
Strictly Descending: [3, 2, 1] → Returns "descending"
Mixed Pattern: [1, 3, 2] → Returns "not sorted"
Two Elements: [5, 3] → Returns "descending"

How Solutions Handle Edge Cases:

Length checks prevent invalid array access
Proper initialization handles boundary conditions
Clear distinction between equal elements and sorting direction
Consistent behavior for edge cases

Test Cases

def test_check_if_sorted():
    # Ascending order
    assert check_if_sorted([1, 2, 3, 4, 5]) == "ascending"
    
    # Descending order
    assert check_if_sorted([5, 4, 3, 2, 1]) == "descending"
    
    # Not sorted
    assert check_if_sorted([1, 3, 2, 4]) == "not sorted"
    
    # All equal
    assert check_if_sorted([1, 1, 1, 1]) == "ascending"
    
    # Empty array
    assert check_if_sorted([]) == "ascending"
    
    # Single element
    assert check_if_sorted([7]) == "ascending"
    
    # Two elements ascending
    assert check_if_sorted([3, 5]) == "ascending"
    
    # Two elements descending
    assert check_if_sorted([5, 3]) == "descending"
    
    # Ascending with duplicates
    assert check_if_sorted([1, 2, 2, 3]) == "ascending"
    
    # Descending with duplicates
    assert check_if_sorted([3, 2, 2, 1]) == "descending"
    
    print("All tests passed!")

test_check_if_sorted()

Follow-up Questions

Strict vs Non-Strict: How would you check for strictly ascending/descending (no equal elements)?
Custom Comparator: How would you handle custom sorting criteria?
Partially Sorted: How would you check if an array is sorted except for k elements?
Multiple Criteria: How would you handle sorting by multiple fields?
Stream Processing: How would you check sorting status for a data stream?

Common Mistakes

Incorrect Edge Case Handling: Not handling empty or single-element arrays
- Problem: Runtime errors or incorrect results
- Solution: Explicit checks at the beginning
Wrong Equality Logic: Not handling equal consecutive elements properly
- Problem: Treating equal elements as violating sort order
- Solution: Use <= and >= for comparisons
Missing Early Termination: Continuing to check after finding mixed patterns
- Problem: Unnecessary computation
- Solution: Return immediately when both patterns are found
Inconsistent Return Values: Not having a clear standard for edge cases
- Problem: Confusing behavior for boundary conditions
- Solution: Establish clear conventions (e.g., empty array is “ascending”)

Interview Tips

Clarify Requirements: Ask about handling of equal elements and edge cases
Start Simple: Begin with the basic single-pass approach
Discuss Optimizations: Mention early termination benefits
Consider Alternatives: Briefly mention the sorting comparison approach
Test Edge Cases: Walk through empty, single-element, and all-equal scenarios

Concept Explanations

Linear Validation Pattern: This problem demonstrates the pattern of validating array properties in a single pass, which is fundamental for many array analysis problems.

State Tracking: Learning to track multiple boolean states (ascending/descending patterns) during iteration is a valuable technique for complex validation problems.

When to Apply: Use this pattern when you need to validate sequential properties of data, such as checking trends, monotonicity, or order constraints in any sequence.