Ask a Question

Back to Problem

All categories
OJ (933)
- Two Sum (22)
- Add Two Numbers (11)
- Longest Substring Without Repeating Characters (5)
- Median of Two Sorted Arrays (8)
- Longest Palindromic Substring (10)
- ZigZag Conversion (12)
- Reverse Integer (2)
- String to Integer (atoi) (9)
- Palindrome Number (4)
- Regular Expression Matching (15)
- Container With Most Water (2)
- Integer to Roman (4)
- Roman to Integer (1)
- Longest Common Prefix (3)
- 3Sum (15)
- 3Sum Closest (1)
- Letter Combinations of a Phone Number (4)
- 4Sum (8)
- Remove Nth Node From End of List (1)
- Valid Parentheses (1)
- Merge Two Sorted Lists (2)
- Generate Parentheses (4)
- Merge k Sorted Lists (2)
- Swap Nodes in Pairs (5)
- Reverse Nodes in k-Group (1)
- Remove Duplicates from Sorted Array (7)
- Remove Element (3)
- Implement strStr() (8)
- Divide Two Integers (9)
- Substring with Concatenation of All Words (2)
- Next Permutation (2)
- Longest Valid Parentheses (3)
- Search in Rotated Sorted Array (4)
- Search for a Range (2)
- Search Insert Position (1)
- Valid Sudoku (6)
- Sudoku Solver (6)
- Count and Say (7)
- Combination Sum (7)
- Combination Sum II (1)
- First Missing Positive (2)
- Trapping Rain Water (2)
- Multiply Strings (6)
- Wildcard Matching (6)
- Jump Game II (1)
- Permutations (7)
- Permutations II (6)
- Rotate Image (3)
- Anagrams (8)
- Pow(x, n) (9)
- N-Queens (4)
- N-Queens II (3)
- Maximum Subarray (3)
- Spiral Matrix (4)
- Jump Game (5)
- Merge Intervals (6)
- Insert Interval (2)
- Length of Last Word (0)
- Spiral Matrix II (0)
- Permutation Sequence (0)
- Rotate List (7)
- Unique Paths (1)
- Unique Paths II (4)
- Minimum Path Sum (1)
- Valid Number (11)
- Plus One (2)
- Add Binary (2)
- Text Justification (8)
- Sqrt(x) (5)
- Climbing Stairs (5)
- Simplify Path (1)
- Edit Distance (2)
- Set Matrix Zeroes (3)
- Search a 2D Matrix (1)
- Sort Colors (5)
- Minimum Window Substring (3)
- Combinations (2)
- Subsets (4)
- Word Search (6)
- Remove Duplicates from Sorted Array II (5)
- Search in Rotated Sorted Array II (1)
- Remove Duplicates from Sorted List II (1)
- Remove Duplicates from Sorted List (3)
- Largest Rectangle in Histogram (3)
- Maximal Rectangle (4)
- Partition List (2)
- Scramble String (5)
- Merge Sorted Array (9)
- Gray Code (7)
- Subsets II (1)
- Decode Ways (4)
- Reverse Linked List II (3)
- Restore IP Addresses (3)
- Binary Tree Inorder Traversal (6)
- Unique Binary Search Trees II (7)
- Unique Binary Search Trees (3)
- Interleaving String (5)
- Validate Binary Search Tree (4)
- Recover Binary Search Tree (10)
- Same Tree (2)
- Symmetric Tree (6)
- Binary Tree Level Order Traversal (2)
- Binary Tree Zigzag Level Order Traversal (3)
- Maximum Depth of Binary Tree (6)
- Construct Binary Tree from Preorder and Inorder Traversal (6)
- Construct Binary Tree from Inorder and Postorder Traversal (3)
- Binary Tree Level Order Traversal II (1)
- Convert Sorted Array to Binary Search Tree (5)
- Convert Sorted List to Binary Search Tree (4)
- Balanced Binary Tree (4)
- Minimum Depth of Binary Tree (4)
- Path Sum (5)
- Path Sum II (5)
- Flatten Binary Tree to Linked List (6)
- Distinct Subsequences (3)
- Populating Next Right Pointers in Each Node (5)
- Populating Next Right Pointers in Each Node II (7)
- Pascal's Triangle (4)
- Pascal's Triangle II (3)
- Triangle (9)
- Best Time to Buy and Sell Stock (4)
- Best Time to Buy and Sell Stock II (8)
- Best Time to Buy and Sell Stock III (3)
- Binary Tree Maximum Path Sum (12)
- Valid Palindrome (7)
- Word Ladder II (15)
- Word Ladder (20)
- Longest Consecutive Sequence (6)
- Sum Root to Leaf Numbers (5)
- Surrounded Regions (10)
- Palindrome Partitioning (4)
- Palindrome Partitioning II (6)
- Clone Graph (11)
- Gas Station (9)
- Candy (16)
- Single Number (11)
- Single Number II (6)
- Copy List with Random Pointer (11)
- Word Break (11)
- Word Break II (17)
- Linked List Cycle (5)
- Linked List Cycle II (12)
- Reorder List (11)
- Binary Tree Preorder Traversal (8)
- Binary Tree Postorder Traversal (7)
- LRU Cache (37)
- Insertion Sort List (14)
- Sort List (27)
- Max Points on a Line (32)
- Evaluate Reverse Polish Notation (20)
- Reverse Words in a String (19)

Is the input array always sorted ?

1 Answer

No. There is a test case which is unsorted. I implemented a quick sort.

Does anyone have a better solution without sorting the input?

answered Feb 10 by yongkangliu (200 points)

the result is in non-descending order, so we cant go over sorting part. so sorting input is the most efficient way.

commented Feb 23 by yuruofeifei (150 points)

...

Is the input array always sorted ?

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

Please log in or register to add a comment.