Check if Numbers Are Ascending in a Sentence - Solution & Explanation
Problem Statement
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.
- For example,
"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 <= 200sconsists of lowercase English letters, spaces, and digits from0to9, inclusive.- The number of tokens in
sis between2and100, inclusive. - The tokens in
sare separated by a single space. - There are at least two numbers in
s. - Each number in
sis a positive number less than100, with no leading zeros. scontains no leading or trailing spaces.
Approach Overview
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 1: Simple Iteration with Integer Conversion
In this approach, the goal is to parse through the sentence to extract the numbers, convert them to integers, and check if they are in strictly increasing order. This is achieved by splitting the input string into tokens and identifying the numerical tokens based on we can convert them to integers. Then we iterate over these integers and ensure each is greater than its predecessor.
This C program checks if numbers in the given sentence string are strictly increasing. The strtok function splits the string into tokens, and isdigit checks if a token is a number. If it is, atoi converts it to an integer. We maintain a `prev` variable initialized to -1 to keep track of the last seen number and ensure each subsequent number is greater.
Complexity
Time Complexity: O(n), where n is the length of string `s`. We iterate over the string once.
Space Complexity: O(1), since we use a fixed amount of extra space.
Approach 2: Regular Expression Filtering
This approach uses regular expressions to directly extract numbers from the input string. This method isolates the process of filtering out numbers, allowing the rest of the logic to focus on verifying the numbers are in strictly increasing order by comparing each to the previous number registered.
This C++ solution uses regular expressions to extract all numbers from the string. It uses `sregex_iterator` with a regular expression `\\b\\d+\\b` that matches whole number tokens in the string. Each number is checked to ensure it is larger than the previous one encountered, enforcing a strictly increasing order.
Complexity
Time Complexity: O(n), where n is the length of the string `s` given only digits and their positions matter.
Space Complexity: O(1), as no additional data structures are used for storage.
Approach 3: Simulation
We can split the string s into several words by spaces. Then, for each word, check if it is a number. If it is a number, convert it to an integer, compare it with the previous number. If it is not strictly increasing, return false. Otherwise, assign the current number to the previous number and continue the traversal.
If the traversal ends, it means that the numbers in the string are strictly increasing, so return true.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Simple Iteration with Integer Conversion | Time Complexity: O(n), where n is the length of string `s`. We iterate over the string once. |
| Regular Expression Filtering | Time Complexity: O(n), where n is the length of the string `s` given only digits and their positions matter. |
| Simulation | — |
Detailed Complexity Analysis
| 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. |
Video Solution
2042. Check if Numbers Are Ascending in a Sentence (Leetcode Easy) • Programming Live with Larry • 647 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check if Numbers Are Ascending in a Sentence easy or hard?
Check if Numbers Are Ascending in a Sentence Python/Java solution
How to solve Check if Numbers Are Ascending in a Sentence in O(n)?
What is the best approach for Check if Numbers Are Ascending in a Sentence?
Is Check if Numbers Are Ascending in a Sentence asked at Google/Amazon/Meta?
What data structure is used in Check if Numbers Are Ascending in a Sentence?
What is the time complexity of Check if Numbers Are Ascending in a Sentence?
Ready to solve this problem?
Practice Check if Numbers Are Ascending in a Sentence with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor