Watch 10 video solutions for Check if Numbers Are Ascending in a Sentence, a easy level problem involving String. This walkthrough by Programming Live with Larry has 643 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A sentence is a list of tokens separated by a single space with no leading or trailing spaces. Every token is either a positive number consisting of digits 0-9 with no leading zeros, or a word consisting of lowercase English letters.
"a puppy has 2 eyes 4 legs" is a sentence with seven tokens: "2" and "4" are numbers and the other tokens such as "puppy" are words.Given a string s representing a sentence, you need to check if all the numbers in s are strictly increasing from left to right (i.e., other than the last number, each number is strictly smaller than the number on its right in s).
Return true if so, or false otherwise.
Example 1:
Input: s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles" Output: true Explanation: The numbers in s are: 1, 3, 4, 6, 12. They are strictly increasing from left to right: 1 < 3 < 4 < 6 < 12.
Example 2:
Input: s = "hello world 5 x 5" Output: false Explanation: The numbers in s are: 5, 5. They are not strictly increasing.
Example 3:
Input: s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s" Output: false Explanation: The numbers in s are: 7, 51, 50, 60. They are not strictly increasing.
Constraints:
3 <= s.length <= 200s consists of lowercase English letters, spaces, and digits from 0 to 9, inclusive.s is between 2 and 100, inclusive.s are separated by a single space.s.s is a positive number less than 100, with no leading zeros.s contains no leading or trailing spaces.Problem Overview: Given a sentence containing words and integers separated by spaces, verify that every number appears in strictly increasing order from left to right. You only compare the numbers that appear in the sentence while ignoring the words.
Approach 1: Simple Iteration with Integer Conversion (O(n) time, O(1) space)
Scan the sentence token by token and extract numbers as you encounter them. Split the string by spaces, then check each token using isdigit() (or equivalent). Convert numeric tokens to integers and compare them with the previous number seen. If the current number is less than or equal to the previous one, the sequence is not strictly increasing and you return false. This approach performs a single pass through the sentence, making it the most straightforward solution for string parsing problems.
The key insight is that you do not need to store all numbers. Track only the last seen number and compare as you iterate. Each token check and conversion happens once, giving linear time complexity O(n) where n is the length of the sentence, and constant extra space O(1). This method works in every language and is typically the first implementation developers write during interviews.
Approach 2: Regular Expression Filtering (O(n) time, O(k) space)
Instead of checking every token manually, use a regular expression to extract only the numeric substrings. A pattern like \d+ captures all integer values in the sentence. After collecting these matches, convert them to integers and iterate through the list to verify that each number is strictly larger than the previous one.
This approach separates extraction and validation. The regex engine scans the entire string once to produce k numbers, then a second pass verifies ordering. Time complexity remains O(n), but space becomes O(k) because all extracted numbers are stored before comparison. Regex-based parsing is common in problems involving regular expressions and structured string processing.
Recommended for interviews: The simple iteration approach is what interviewers usually expect. It demonstrates that you can parse a sentence, detect numeric tokens, and maintain a running comparison in a single pass. The regex approach is concise and readable but relies on library utilities, while the iteration method shows stronger understanding of basic string processing and space optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Iteration with Integer Conversion | O(n) | O(1) | Best general solution. One pass through the sentence with minimal memory. |
| Regular Expression Filtering | O(n) | O(k) | Useful when regex utilities are available and extracting numbers is easier than manual parsing. |