algoadvance

Leetcode 2042. Check if Numbers Are Ascending in a Sentence

Problem Statement

You are given a string s representing a sentence containing words and numbers. Your task is to determine if the numbers in the sentence are strictly ascending.

A sentence is a list of tokens separated by a single space. Tokens can be either words or numbers. A word consists of only lowercase English letters, while a number consists of only digits.

Return true if the numbers in s are strictly ascending, otherwise return false.

Clarifying Questions

1. Input Constraints:
   • The string s will only contain lowercase English letters, digits, and spaces.
   • There is at least one token in the string.
2. Output:
   • Return true if all numbers in the sentence are in strictly ascending order.
   • Return false otherwise.
3. Edge Cases:
   • Sentences without any numbers.
   • Sentences with one number.
   • Mixed sequences of words and numbers.

Strategy

1. Tokenization:
   • Split the string s by spaces to isolate individual tokens.
2. Identifying Numbers:
   • Check each token to determine if it is a number or a word.
   • If it is a number (all characters are digits), compare it with the previous number to ensure the numbers are in ascending order.
3. Comparison:
   • Maintain a variable to track the last seen number.
   • Ensure each new number is greater than the last seen number.

Code

#include <string>
#include <sstream>
#include <climits>
#include <iostream>

bool areNumbersAscending(std::string s) {
    std::istringstream stream(s);
    std::string token;
    int prevNumber = INT_MIN;

    while (stream >> token) {
        // Check if the token is a number
        bool isNumber = true;
        for (char c : token) {
            if (!isdigit(c)) {
                isNumber = false;
                break;
            }
        }

        if (isNumber) {
            int number = std::stoi(token);
            if (number <= prevNumber) {
                return false;
            }
            prevNumber = number;
        }
    }

    return true;
}

// Sample Usage
int main() {
    std::string s1 = "1 box has 3 blue 4 red 7 green and 8 yellow marbles";
    std::string s2 = "5 hello 2 world";
    std::string s3 = "this is a test 1 2 3";

    std::cout << std::boolalpha << areNumbersAscending(s1) << std::endl; // True
    std::cout << std::boolalpha << areNumbersAscending(s2) << std::endl; // False
    std::cout << std::boolalpha << areNumbersAscending(s3) << std::endl; // True

    return 0;
}

Time Complexity

• Tokenization and Checking: Each token is processed exactly once.
  • Splitting the string and iterating through tokens is O(n), where n is the number of characters in the string.
  • Checking if a token is a number is O(m), where m is the length of the token.
  • Overall complexity is O(n) as we iterate through all characters once.

In total, the time complexity is O(n), which is efficient for the problem constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?