Leetcode MEDIUM 3204 - Bitwise User Permissions Analysis - Explained by Everyday Data Science
Bitwise User Permissions Analysis - Video Solution
Watch 4 video solutions for Bitwise User Permissions Analysis, a medium level problem involving Database. This walkthrough by Everyday Data Science has 436 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Table: user_permissions
+-------------+---------+ | Column Name | Type | +-------------+---------+ | user_id | int | | permissions | int | +-------------+---------+ user_id is the primary key. Each row of this table contains the user ID and their permissions encoded as an integer.
Consider that each bit in the permissions integer represents a different access level or feature that a user has.
Write a solution to calculate the following:
- common_perms: The access level granted to all users. This is computed using a bitwise AND operation on the
permissionscolumn. - any_perms: The access level granted to any user. This is computed using a bitwise OR operation on the
permissionscolumn.
Return the result table in any order.
The result format is shown in the following example.
Example:
Input:
user_permissions table:
+---------+-------------+ | user_id | permissions | +---------+-------------+ | 1 | 5 | | 2 | 12 | | 3 | 7 | | 4 | 3 | +---------+-------------+
Output:
+-------------+--------------+
| common_perms | any_perms |
+--------------+-------------+
| 0 | 15 |
+--------------+-------------+
Explanation:
- common_perms: Represents the bitwise AND result of all permissions:
- For user 1 (5): 5 (binary 0101)
- For user 2 (12): 12 (binary 1100)
- For user 3 (7): 7 (binary 0111)
- For user 4 (3): 3 (binary 0011)
- Bitwise AND: 5 & 12 & 7 & 3 = 0 (binary 0000)
- any_perms: Represents the bitwise OR result of all permissions:
- Bitwise OR: 5 | 12 | 7 | 3 = 15 (binary 1111)
Approach Overview
Problem Overview: You are given a table where each user’s permissions are encoded as a bitmask. Each bit represents a capability (read, write, execute, admin, etc.). The task is to analyze these bitwise permission values using SQL and return aggregated information about which permissions are enabled.
Approach 1: Bit Decomposition with Shifts (O(n * b) time, O(1) space)
The straightforward approach inspects every permission bit individually. For each row, shift the permission integer right by the bit position and check the least significant bit using (permissions >> k) & 1. In SQL this usually appears as conditional expressions or repeated calculations for each permission flag. This works when the number of permission types is small and fixed. Time complexity is O(n * b) where n is the number of rows and b is the number of permission bits examined.
Approach 2: Bitwise AND Filtering (O(n) time, O(1) space)
The optimal solution relies on direct bitwise checks using permissions & mask. Each permission corresponds to a mask such as 1, 2, 4, 8, etc. In MySQL, you can test whether a permission exists by evaluating whether (permissions & mask) != 0. This allows filtering, counting, or grouping users based on enabled bits without decomposing the entire number. Because each row is evaluated once, the query runs in O(n) time with constant space.
This pattern works well for analytics queries such as counting how many users have a specific permission, checking combinations of permissions, or deriving permission flags dynamically. SQL engines efficiently evaluate bitwise expressions during scans, making the approach scalable even for large tables.
Problems like this commonly appear in database systems where compact bitmasks store feature flags or access control lists. Understanding bitwise operations also helps when working with permission models, feature toggles, or system flags stored as integers.
Related concepts include bitwise operations, SQL querying, and general database data modeling strategies.
Recommended for interviews: The bitwise AND filtering approach is what interviewers expect. It shows that you understand how permission bitmasks are designed and how to query them efficiently. Demonstrating the naive bit-decomposition approach first shows conceptual understanding, but the optimized bitwise check proves you can translate that idea into an efficient SQL query.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Decomposition with Shifts | O(n * b) | O(1) | When analyzing each permission bit separately or when the query explicitly requires checking multiple fixed bit positions |
| Bitwise AND Filtering | O(n) | O(1) | General case for permission checks, filtering users by specific flags, or aggregating permission counts efficiently |