Invalid Tweets

Difficulty: Easy | Acceptance: 85.10% | Paid: No Topics: Database

Table: Tweets

+----------------+---------+ | Column Name | Type | +----------------+---------+ | tweet_id | int | | content | varchar | +----------------+---------+ tweet_id is the primary key (column with unique values) for this table. This table contains all the tweets in a social media app.

Write a solution to find the IDs of the invalid tweets. The tweet is invalid if the content of the tweet exceeds 15 characters.

The result format is in the following example.

• Examples
• Constraints
• Approach 1: Using Built-in Length Function
• Approach 2: Using Regular Expressions
• Approach 3: Iterative Character Count

Examples

Example 1:

Input: Tweets table: +----------+----------------------------------+ | tweet_id | content | +----------+----------------------------------+ | 1 | Vote for Biden | | 2 | Let us make America great again! | +----------+----------------------------------+

Output: +----------+ | tweet_id | +----------+ | 2 | +----------+

Explanation: Tweet 1 has length = 14 characters. It is a valid tweet. Tweet 2 has length = 32 characters. It is an invalid tweet.

Constraints

1 <= tweet_id <= 10⁴
1 <= content.length <= 10⁴
The table may contain at most 10⁵ rows.
content consists of English letters, spaces, and punctuation marks.

Approach 1: Using Built-in Length Function

Intuition The most direct way to determine if a tweet is invalid is to check the length of the content string using the language’s built-in string length method. If the length is strictly greater than 15, the tweet ID should be included in the result.

Steps

• Iterate through the list of tweet records.
• For each record, access the content field.
• Check if the length of the content is greater than 15.
• If the condition is met, add the tweet_id to the result list.
• Return the result list.

class Solution:
    def invalidTweets(self, tweets: list[dict]) -> list[int]:
        # Simulating database query: SELECT tweet_id FROM Tweets WHERE LENGTH(content) > 15
        return [t['tweet_id'] for t in tweets if len(t['content']) > 15]

Complexity

• Time: O(N * L), where N is the number of tweets and L is the average length of the content. Calculating the length of a string typically takes O(L) time.
• Space: O(K), where K is the number of invalid tweets, to store the result.
• Notes: This is the most idiomatic and efficient approach for general-purpose programming languages.

Approach 2: Using Regular Expressions

Intuition We can use a regular expression to match strings that have a length of at least 16 characters. The pattern .{16,} matches any character (except a line terminator) 16 or more times. This approach shifts the logic of length checking to the regex engine.

Steps

• Define a regular expression pattern that matches 16 or more characters.
• Iterate through the list of tweet records.
• For each record, test if the content matches the pattern.
• If it matches, the tweet is invalid; add the ID to the result list.
• Return the result list.

import re

class Solution:
    def invalidTweets(self, tweets: list[dict]) -> list[int]:
        # Simulating database query: SELECT tweet_id FROM Tweets WHERE content REGEXP '.{16,}'
        pattern = re.compile(r'.{16,}')
        return [t['tweet_id'] for t in tweets if pattern.match(t['content'])]

Complexity

• Time: O(N * L), where N is the number of tweets and L is the average length of the content. Regex matching generally requires scanning the string.
• Space: O(K) for the result, plus O(1) or O(M) for the regex compilation depending on the language implementation.
• Notes: While flexible, regex is often slower than a direct length check for simple constraints like this.

Approach 3: Iterative Character Count

Intuition Instead of relying on a built-in length function, we can manually iterate through the characters of the content string and count them. If the count exceeds 15, we can immediately stop counting and mark the tweet as invalid. This mimics how a database engine might process a LENGTH function at a lower level.

Steps

• Initialize an empty result list.
• Iterate through each tweet record.
• Initialize a counter to 0.
• Loop through each character in the content string:
  • Increment the counter.
  • If the counter becomes 16, break the loop (we know it’s invalid).
• If the counter reached 16, add the tweet_id to the result list.
• Return the result list.

class Solution:
    def invalidTweets(self, tweets: list[dict]) -> list[int]:
        # Simulating manual length check
        result = []
        for t in tweets:
            count = 0
            for _ in t['content']:
                count += 1
                if count > 15:
                    result.append(t['tweet_id'])
                    break
        return result

Complexity

• Time: O(N * L), where N is the number of tweets and L is the average length of the content. In the worst case (valid tweets), we scan the whole string.
• Space: O(K) for the result list.
• Notes: This approach is functionally equivalent to the built-in length check but demonstrates the underlying algorithm. It can be slightly more efficient if we only need to know if the length exceeds a threshold (early termination), whereas length() might calculate the full length depending on implementation.