Invalid Transactions - Practice Coding Problems

Invalid Transactions - Problem

A transaction is possibly invalid if:

The amount exceeds $1000, or
It occurs within (and including) 60 minutes of another transaction with the same name in a different city

You are given an array of strings transactions where transactions[i] consists of comma-separated values representing the name, time (in minutes), amount, and city of the transaction.

Return a list of transactions that are possibly invalid. You may return the answer in any order.

Input & Output

Example 1 — Basic Invalid Transactions

$ Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"]

› Output: ["alice,20,800,mtv","alice,50,100,beijing"]

💡 Note: Both transactions are invalid: alice made transactions in different cities (mtv vs beijing) within 60 minutes (time difference = 30 minutes ≤ 60)

Example 2 — Amount Limit Violation

$ Input: transactions = ["alice,20,800,mtv","alice,50,1200,beijing"]

› Output: ["alice,20,800,mtv","alice,50,1200,beijing"]

💡 Note: alice,50,1200,beijing is invalid due to amount > $1000. alice,20,800,mtv is invalid due to location conflict within 60 minutes

Example 3 — Valid Transactions

$ Input: transactions = ["alice,20,800,mtv","bob,50,1200,mtv"]

› Output: ["bob,50,1200,mtv"]

💡 Note: alice's transaction is valid (amount ≤ 1000, no conflicts). bob's transaction is invalid due to amount > $1000

Constraints

transactions.length == n
1 ≤ n ≤ 1000
Each transactions[i] takes the form "{name},{time},{amount},{city}"
Each {name} and {city} consist of lowercase English letters, and have lengths between 1 and 10
Each {time} is given as integers between 0 and 1000
Each {amount} is given as integers between 0 and 2000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of transaction strings with name,time,amount,city format

Process

Check amount > 1000 OR same name in different cities within 60 minutes

Output

List of all transactions that violate either condition

Key Takeaway

🎯 Key Insight: A transaction is invalid if amount > $1000 OR same person appears in different cities within 60 minutes

Asked in

a Amazon 12 G Google 8 M Microsoft 6 f Facebook 4

The key insight is to check two violation conditions: amount exceeding $1000 and same person in different cities within 60 minutes. Best approach uses hash map grouping to organize transactions by person name first. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Group by Name	O(n²)	O(n)	Group transactions by name first, then check constraints within each group
Brute Force - Compare All Pairs	O(n²)	O(1)	Check each transaction against every other transaction

Hash Map - Group by Name — Algorithm Steps

Parse all transactions
Group transactions by name using hash map
For each person's transactions, check amount limits
Within each group, check for time/location conflicts

Visualization

Tap to expand

Step-by-Step Walkthrough

Group by Name

Create hash map with name as key, transactions as values

Check Within Groups

Only compare transactions within same name group

Validate Constraints

Check amount limits and time/location conflicts

Collect Results

Gather all invalid transactions

Code -

solution.c — C

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

typedef struct {
    int index;
    char name[50];
    int time;
    int amount;
    char city[50];
} Transaction;

char** solution(char** transactions, int transactionsSize, int* returnSize) {
    Transaction* trans = (Transaction*)malloc(transactionsSize * sizeof(Transaction));
    int* invalid = (int*)malloc(transactionsSize * sizeof(int));
    *returnSize = 0;
    
    // Parse all transactions
    for (int i = 0; i < transactionsSize; i++) {
        char* copy = strdup(transactions[i]);
        char* name = strtok(copy, ",");
        char* timeStr = strtok(NULL, ",");
        char* amountStr = strtok(NULL, ",");
        char* city = strtok(NULL, ",");
        
        trans[i].index = i;
        strcpy(trans[i].name, name);
        trans[i].time = atoi(timeStr);
        trans[i].amount = atoi(amountStr);
        strcpy(trans[i].city, city);
        
        free(copy);
    }
    
    // Check each transaction
    for (int i = 0; i < transactionsSize; i++) {
        int isInvalid = 0;
        
        // Check amount limit
        if (trans[i].amount > 1000) {
            isInvalid = 1;
        } else {
            // Check for conflicts with same name
            for (int j = 0; j < transactionsSize; j++) {
                if (i != j && strcmp(trans[i].name, trans[j].name) == 0 && 
                    strcmp(trans[i].city, trans[j].city) != 0 && 
                    abs(trans[i].time - trans[j].time) <= 60) {
                    isInvalid = 1;
                    break;
                }
            }
        }
        
        if (isInvalid) {
            invalid[(*returnSize)++] = i;
        }
    }
    
    char** result = (char**)malloc(*returnSize * sizeof(char*));
    for (int i = 0; i < *returnSize; i++) {
        result[i] = strdup(transactions[invalid[i]]);
    }
    
    free(trans);
    free(invalid);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing for array of strings
    char** transactions = (char**)malloc(1000 * sizeof(char*));
    int count = 0;
    
    char* ptr = line + 1; // Skip [
    while (*ptr && *ptr != ']') {
        if (*ptr == '"') {
            ptr++;
            char* start = ptr;
            while (*ptr && *ptr != '"') ptr++;
            int len = ptr - start;
            transactions[count] = (char*)malloc((len + 1) * sizeof(char));
            strncpy(transactions[count], start, len);
            transactions[count][len] = '\0';
            count++;
            if (*ptr) ptr++;
        }
        if (*ptr == ',') ptr++;
        while (*ptr == ' ') ptr++;
    }
    
    int returnSize;
    char** result = solution(transactions, count, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case, all transactions belong to one person, still need to compare all pairs within that group

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map stores all transactions grouped by name

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 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

Hash Map - Group by Name — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler