Check if Numbers Are Ascending in a Sentence

Check if Numbers Are Ascending in a Sentence - Problem

String Easy

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.

Input & Output

Example 1 — Numbers in Ascending Order

$ Input: s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"

› Output: true

💡 Note: The numbers are 1, 3, 4, 6, 12 which are in strictly increasing order: 1 < 3 < 4 < 6 < 12

Example 2 — Numbers Not in Ascending Order

$ Input: s = "hello world 5 x 1"

› Output: false

💡 Note: The numbers are 5, 1 which are not in strictly increasing order since 5 > 1

Example 3 — Equal Numbers

$ Input: s = "sunset is at 7 7 pm"

› Output: false

💡 Note: The numbers are 7, 7 which are not strictly increasing since 7 = 7 (not strictly greater)

Constraints

3 ≤ s.length ≤ 200
s consists of lowercase English letters, spaces, and digits from 0 to 9
The number of tokens in s is between 2 and 100

Visualization

Tap to expand

Understanding the Visualization

Parse Sentence

Split into tokens and identify numbers

Check Order

Compare each number with the previous

Return Result

True if ascending, false otherwise

Key Takeaway

🎯 Key Insight: Only need to track the last number seen while scanning left to right

Asked in

a Amazon 15 M Microsoft 8 G Google 5

The key insight is to parse the sentence and compare each number with the previous one. The optimal approach uses a single pass to check numbers immediately when found. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass with Comparison	O(n)	O(1)	Check numbers on the fly during a single pass through the sentence
Extract All Numbers Then Check	O(n)	O(k)	Extract all numbers from the sentence, then verify they're in strictly increasing order

Single Pass with Comparison — Algorithm Steps

Split sentence into tokens
For each numeric token, compare with previous number
Return false if any number is not strictly greater

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Tokens

Check each token one by one

Compare Numbers

Compare with previous number

Early Decision

Return result immediately

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int isNumber(char* token) {
    for (int i = 0; token[i]; i++) {
        if (!isdigit(token[i])) return 0;
    }
    return strlen(token) > 0;
}

int solution(char* s) {
    char* copy = malloc(strlen(s) + 1);
    strcpy(copy, s);
    
    int lastNumber = -1;
    
    char* token = strtok(copy, " ");
    while (token != NULL) {
        if (isNumber(token)) {
            int currentNumber = atoi(token);
            if (lastNumber != -1 && currentNumber <= lastNumber) {
                free(copy);
                return 0;
            }
            lastNumber = currentNumber;
        }
        token = strtok(NULL, " ");
    }
    
    free(copy);
    return 1;
}

int main() {
    char s[10001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the sentence, where n is the length of the sentence

✓ Linear Growth

Space Complexity

O(1)

Only stores the last seen number and current token, constant extra space

✓ Linear Space

21.8K Views

Medium Frequency

~10 min Avg. Time

750 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass with Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler