LeetCode 1890 - The Latest Login in 2020

The problem provides a database table Logins that records user login events, with columns userid and timestamp. Each combination of (userid, timestamp) is unique, ensuring that every row corresponds to a distinct login.

leetcodeeasydatabase

LeetCode Problem 1890

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem provides a database table Logins that records user login events, with columns user_id and time_stamp. Each combination of (user_id, time_stamp) is unique, ensuring that every row corresponds to a distinct login. The task is to determine, for each user who logged in at least once during the year 2020, the latest login timestamp in that year. Users who did not log in during 2020 should be excluded from the output.

In essence, the input is a set of login events across multiple years, and the expected output is a table with two columns: user_id and last_stamp, where last_stamp is the most recent login of that user in 2020. Important points include filtering by year 2020 and correctly identifying the maximum timestamp per user. Edge cases include users with multiple logins in 2020, users with no logins in 2020, and timestamps at the boundary of 2020 (like 2020-01-01 00:00:00 or 2020-12-31 23:59:59).

Approaches

The simplest approach is brute force. One could iterate over all logins, filter out rows not in 2020, and then for each user, track the latest timestamp seen so far. While this is conceptually correct, it requires iterating multiple times or performing a join/aggregation in SQL without leveraging built-in functions, which could be inefficient for large datasets.

The optimal approach leverages SQL aggregation. By filtering logins to only those in 2020, and then grouping by user_id, we can directly apply the MAX() function on time_stamp to find the latest login per user. This takes advantage of SQL's set-based operations and avoids manual iteration.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(u) Iterate through all logins, store latest per user in memory (u = number of users)
Optimal O(n) O(u) Filter in SQL for 2020, group by user_id, compute MAX per group

Algorithm Walkthrough

  1. Filter the Logins table to retain only rows where time_stamp falls in the year 2020. This ensures we exclude logins from other years.
  2. Group the filtered rows by user_id. This step collects all login timestamps for each user in 2020 into a logical group.
  3. Apply the aggregation function MAX(time_stamp) to each group to determine the latest login timestamp for that user.
  4. Return a table with user_id and last_stamp columns, where last_stamp is the computed maximum timestamp for each user. The order of rows is irrelevant.

Why it works: SQL's GROUP BY with MAX() guarantees that, for each user, the maximum timestamp is selected, and filtering ensures only logins within 2020 are considered. This ensures correctness without missing any users or including invalid years.

Python Solution

Although this is a database problem, we can simulate it in Python using a dictionary to represent groups.

from typing import List, Dict
from datetime import datetime

def latest_login(logins: List[Dict[str, str]]) -> List[Dict[str, str]]:
    latest_per_user = {}
    
    for row in logins:
        user_id = row['user_id']
        timestamp = datetime.strptime(row['time_stamp'], '%Y-%m-%d %H:%M:%S')
        
        if timestamp.year == 2020:
            if user_id not in latest_per_user or timestamp > latest_per_user[user_id]:
                latest_per_user[user_id] = timestamp
    
    result = [{'user_id': uid, 'last_stamp': latest_per_user[uid].strftime('%Y-%m-%d %H:%M:%S')} 
              for uid in latest_per_user]
    
    return result

The Python implementation iterates through all login rows, filters for 2020, and maintains a dictionary keyed by user_id storing the latest timestamp. At the end, the dictionary is converted into the expected output format.

Go Solution

package main

import (
    "time"
)

type Login struct {
    UserID    int
    TimeStamp string
}

type Result struct {
    UserID    int
    LastStamp string
}

func LatestLogin(logins []Login) []Result {
    latestPerUser := make(map[int]time.Time)
    
    for _, login := range logins {
        t, _ := time.Parse("2006-01-02 15:04:05", login.TimeStamp)
        if t.Year() == 2020 {
            if existing, ok := latestPerUser[login.UserID]; !ok || t.After(existing) {
                latestPerUser[login.UserID] = t
            }
        }
    }
    
    results := []Result{}
    for uid, ts := range latestPerUser {
        results = append(results, Result{UserID: uid, LastStamp: ts.Format("2006-01-02 15:04:05")})
    }
    
    return results
}

In Go, map[int]time.Time is used to store the latest timestamp per user. Parsing and formatting timestamps follow Go conventions. The logic mirrors the Python implementation.

Worked Examples

Example 1 input table:

user_id time_stamp
6 2020-06-30 15:06:07
6 2021-04-21 14:06:06
6 2019-03-07 00:18:15
8 2020-02-01 05:10:53
8 2020-12-30 00:46:50
2 2020-01-16 02:49:50
2 2019-08-25 07:59:08
14 2019-07-14 09:00:00
14 2021-01-06 11:59:59

Step by step in Python:

  • Initialize latest_per_user = {}.

  • Process each row:

  • User 6: 2020-06-30 -> latest[6] = 2020-06-30

  • User 8: 2020-02-01 -> latest[8] = 2020-02-01

  • User 8: 2020-12-30 -> update latest[8] = 2020-12-30

  • User 2: 2020-01-16 -> latest[2] = 2020-01-16

  • Users 6, 8, 2 remain, 14 is excluded.

  • Output table:

user_id last_stamp
6 2020-06-30 15:06:07
8 2020-12-30 00:46:50
2 2020-01-16 02:49:50

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass over all login records to filter and compare timestamps.
Space O(u) Store latest timestamp for each user who logged in during 2020.

Time complexity is linear in the number of login records. Space complexity depends on the number of unique users with 2020 logins.

Test Cases

logins = [
    {'user_id': 6, 'time_stamp': '2020-06-30 15:06:07'},
    {'user_id': 6, 'time_stamp': '2021-04-21 14:06:06'},
    {'user_id': 6, 'time_stamp': '2019-03-07 00:18:15'},
    {'user_id': 8, 'time_stamp': '2020-02-01 05:10:53'},
    {'user_id': 8, 'time_stamp': '2020-12-30 00:46:50'},
    {'user_id': 2, 'time_stamp': '2020-01-16 02:49:50'},
    {'user_id': 2, 'time_stamp': '2019-08-25 07:59:08'},
    {'user_id': 14, 'time_stamp': '2019-07-14 09:00:00'},
    {'user_id': 14, 'time_stamp': '2021-01-06 11:59:59'},
]

result = latest_login(logins)
assert any(r['user_id'] == 6 and r['last_stamp'] == '2020-06-30 15:06:07' for r in result) # latest login for 6
assert any(r['user_id'] == 8 and r['last_stamp'] == '2020-12-30 00:46:50' for r in result) # latest login for 8
assert any(r['user_id'] == 2 and r['last_stamp'] == '2020-01-16 02:49:50' for r in result) # latest login for 2
assert all(r['user_id'] != 14 for r in result) # user 14 should not appear
``