LeetCode 3204 - Bitwise User Permissions Analysis

The problem is asking us to analyze a table of user permissions where each user's permissions are encoded as an integer. Each bit in this integer represents a distinct access level or feature.

leetcodemediumdatabase

LeetCode Problem 3204

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem is asking us to analyze a table of user permissions where each user's permissions are encoded as an integer. Each bit in this integer represents a distinct access level or feature. The goal is to compute two aggregate permission values: common_perms, which represents the set of permissions that every user has, and any_perms, which represents the set of permissions that at least one user has.

In other words, common_perms is obtained by performing a bitwise AND across all users' permissions, because a bit will only remain set if it is set in every user's permission integer. Conversely, any_perms is obtained by performing a bitwise OR across all users' permissions, because a bit will be set if it is present in any user's permissions.

The input is the user_permissions table, where each row contains a user_id and their permissions. The output is a single-row table containing common_perms and any_perms.

Important considerations include handling empty tables, ensuring integer operations handle large bit masks correctly, and correctly performing the aggregation even if permissions are 0. The problem guarantees that user_id is unique, and there may be any number of users.

Approaches

The most straightforward approach is to iterate through all rows and maintain running values for common_perms and any_perms. Initially, common_perms could be set to a value with all bits set, such as the maximum integer size allowed, so that the first bitwise AND is correct. any_perms can start at 0. For each row, we update common_perms with AND and any_perms with OR. While simple and correct, this approach requires manual iteration if implemented in a procedural language. In SQL, a naive approach might attempt multiple nested queries, which is unnecessary since SQL supports aggregate bitwise operators.

The key insight for an optimal SQL solution is that standard SQL provides the aggregate functions BIT_AND and BIT_OR in many RDBMS, allowing a single query to compute both values directly. This eliminates the need for procedural iteration, providing both simplicity and efficiency.

Approach Time Complexity Space Complexity Notes
Brute Force Iteration O(n) O(1) Iterate through all users manually and compute bitwise AND/OR. Correct but verbose in SQL.
Optimal Aggregate O(n) O(1) Use SQL aggregate functions BIT_AND and BIT_OR to compute results in one query efficiently.

Algorithm Walkthrough

  1. Start with the user_permissions table containing user_id and permissions.
  2. Apply the SQL aggregate function BIT_AND to the permissions column. This computes the bitwise AND across all rows, resulting in common_perms.
  3. Apply the SQL aggregate function BIT_OR to the permissions column. This computes the bitwise OR across all rows, resulting in any_perms.
  4. Select both values into a single-row result table. Since the problem allows any output order, no further sorting is required.
  5. Return the result.

Why it works: The bitwise AND of all integers will only keep bits set that are set in every integer, directly representing the permissions that all users have. Similarly, the bitwise OR of all integers will include any bit that is set in at least one integer, representing the union of all user permissions. This guarantees correctness.

Python Solution

import sqlite3
from typing import Tuple

def bitwise_user_permissions_analysis(conn: sqlite3.Connection) -> Tuple[int, int]:
    """
    Compute common_perms and any_perms from the user_permissions table.
    
    Args:
        conn (sqlite3.Connection): A connection object to the database.
    
    Returns:
        Tuple[int, int]: (common_perms, any_perms)
    """
    cursor = conn.cursor()
    cursor.execute("""
        SELECT BITAND(permissions) AS common_perms,
               BITOR(permissions) AS any_perms
        FROM user_permissions
    """)
    result = cursor.fetchone()
    return result

This implementation uses SQL aggregate functions to compute the bitwise AND and OR of the permissions column. The result is retrieved in a single query, returning a tuple (common_perms, any_perms). The Python function simply opens a cursor, executes the aggregate query, and fetches the result.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
    "log"
)

func BitwiseUserPermissionsAnalysis(db *sql.DB) (int, int, error) {
    var commonPerms, anyPerms int
    row := db.QueryRow(`
        SELECT BITAND(permissions) AS common_perms,
               BITOR(permissions) AS any_perms
        FROM user_permissions
    `)
    err := row.Scan(&commonPerms, &anyPerms)
    if err != nil {
        return 0, 0, err
    }
    return commonPerms, anyPerms, nil
}

In Go, the approach is similar. We use QueryRow to execute a single aggregate query and scan the results into commonPerms and anyPerms. We return both values along with any potential error encountered during execution.

Worked Examples

Using the example table:

+---------+-------------+
| user_id | permissions |
+---------+-------------+
| 1       | 5           |
| 2       | 12          |
| 3       | 7           |
| 4       | 3           |
+---------+-------------+

Step by step computation:

Step common_perms any_perms
Initial 1111...1 (all bits set) 0
After user 1 (5=0101) 0101 & 1111...1 = 0101 0
After user 2 (12=1100) 0101 & 1100 = 0000 0101
After user 3 (7=0111) 0000 & 0111 = 0000 1101
After user 4 (3=0011) 0000 & 0011 = 0000 1111

Resulting output:

+-------------+-------------+
| common_perms | any_perms  |
+-------------+-------------+
| 0            | 15         |
+-------------+-------------+

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row of the table is visited once for aggregation.
Space O(1) Only two integer variables are maintained; no extra data structures needed.

The complexity is dominated by the scan of the table, which is linear in the number of users. Memory usage is constant because only the aggregate values are stored.

Test Cases

# Standard case
assert bitwise_user_permissions_analysis(conn) == (0, 15)  # provided example

# Single user
cursor.execute("DELETE FROM user_permissions")
cursor.execute("INSERT INTO user_permissions (user_id, permissions) VALUES (1, 7)")
assert bitwise_user_permissions_analysis(conn) == (7, 7)

# All users with identical permissions
cursor.execute("DELETE FROM user_permissions")
cursor.executemany("INSERT INTO user_permissions (user_id, permissions) VALUES (?, ?)", [(1, 5), (2, 5), (3, 5)])
assert bitwise_user_permissions_analysis(conn) == (5, 5)

# All permissions zero
cursor.execute("DELETE FROM user_permissions")
cursor.executemany("INSERT INTO user_permissions (user_id, permissions) VALUES (?, ?)", [(1, 0), (2, 0)])
assert bitwise_user_permissions_analysis(conn) == (0, 0)

# Mixed zero and non-zero permissions
cursor.execute("DELETE FROM user_permissions")
cursor.executemany("INSERT INTO user_permissions (user_id, permissions) VALUES (?, ?)", [(1, 0), (2, 3)])
assert bitwise_user_permissions_analysis(conn) == (0, 3)
Test Why
Provided example Validates standard bitwise operations
Single user Edge case where only one row exists
Identical permissions Ensures bitwise AND preserves all bits when identical
All zeros Verifies handling of zero values
Mixed zero/non-zero Confirms correctness with partial permission overlap

Edge Cases

One important edge case is when there is only a single user in the table. In this case, both common_perms and any_perms should equal that user's permissions.

A second edge case occurs when all users have zero permissions. The bitwise AND and OR should correctly return zero, and naive implementations that assume non-zero integers may fail.

A third edge case is when the permissions integers are very large, potentially hitting the maximum integer size of the database system. The implementation relies on built-in aggregate functions, which handle integer overflow correctly in most RDBMS, ensuring correctness without additional handling.