Learn a one-pass way to check if array is sorted in non-decreasing order. Intuition, commented Python code, dry run, and clear Big-O analysis included.<\/p>\n\n\n\n
So let’s get started with the [Problem Link<\/span><\/mark><\/a><\/strong>].<\/p>\n\n\n Given an integer array Think of walking from left to right; the moment you step down a hill, you know the landscape is not purely uphill.<\/p>\n\n\n\n1. What does the problem ask?<\/h2>\n\n\n\n
arr<\/code>, decide if it is sorted in non-decreasing order<\/strong> (each element is no larger<\/strong> than the next).
Return True<\/code><\/strong> if the whole array obeys this rule, otherwise return False<\/code><\/strong>.<\/p>\n\n\n\n
\n\n\n\n2. Quick examples<\/h2>\n\n\n\n
arr<\/code><\/th>Output<\/th> Why<\/th><\/tr><\/thead> [1, 2, 2, 5]<\/code><\/td>True<\/code><\/td>Every element \u2264 the next one.<\/td><\/tr> [3, 4, 1]<\/code><\/td>False<\/code><\/td>4 > 1<\/code> breaks the rule.<\/td><\/tr>[7]<\/code><\/td>True<\/code><\/td>A single element is always sorted.<\/td><\/tr> []<\/code><\/td>True<\/code><\/td>An empty list is trivially sorted.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\n\n\n\n3. Intuition & approach<\/h2>\n\n\n\n
\n
arr[i]<\/code> and arr[i + 1]<\/code>.<\/li>\n\n\n\narr[i] \u2264 arr[i+1]<\/code>.<\/li>\n\n\n\n
\n\n\n\n4. Code<\/h2>\n\n\n\n