Table: Employees
+-------------+---------+ | Column Name | Type | +-------------+---------+ | employee_id | int | | name | varchar | +-------------+---------+ employee_id is the column with unique values for this table. Each row of this table indicates the name of the employee whose ID is employee_id.
Table: Salaries
+-------------+---------+ | Column Name | Type | +-------------+---------+ | employee_id | int | | salary | int | +-------------+---------+ employee_id is the column with unique values for this table. Each row of this table indicates the salary of the employee whose ID is employee_id.
Write a solution to report the IDs of all the employees with missing information. The information of an employee is missing if:
Return the result table ordered by employee_id in ascending order.
The result format is in the following example.
Example 1:
Input: Employees table: +-------------+----------+ | employee_id | name | +-------------+----------+ | 2 | Crew | | 4 | Haven | | 5 | Kristian | +-------------+----------+ Salaries table: +-------------+--------+ | employee_id | salary | +-------------+--------+ | 5 | 76071 | | 1 | 22517 | | 4 | 63539 | +-------------+--------+ Output: +-------------+ | employee_id | +-------------+ | 1 | | 2 | +-------------+ Explanation: Employees 1, 2, 4, and 5 are working at this company. The name of employee 1 is missing. The salary of employee 2 is missing.
This approach utilizes SQL's JOIN operations to identify missing information. We can use a FULL OUTER JOIN between the Employees and Salaries tables to ensure we capture all employee IDs, whether they appear in only one of the tables (missing from the other) or in both.
After joining, we will filter the results for rows where either the name or salary is NULL.
This SQL query uses a FULL OUTER JOIN to combine the data from the Employees and Salaries tables on the employee_id. The WHERE clause is used to filter out rows where either the name is NULL or the salary is NULL, indicating missing information from one of the tables.
Time Complexity: O(N + M), where N is the number of employees and M is the number of salaries, because the join operation requires a scan of both tables.
Space Complexity: O(N + M) due to the storage of the join results.
This solution employs two separate queries combined with UNION to find missing records. The first query selects employee_ids from the Employees table that do not exist in the Salaries table (indicating missing salary records), and the second query selects employee_ids from the Salaries table that do not exist in the Employees table (indicating missing employee records).
This SQL script combines two subqueries using UNION: The first subquery lists employee_ids from the Employees table that do not appear in Salaries (missing salaries), and the second lists employee_ids from Salaries that do not appear in Employees (missing names). The result is returned in ascending order by employee_id.
Time Complexity: O(N * M) since each subquery potentially involves a scan of the Employees table for each entry in Salaries, and vice versa.
Space Complexity: O(N + M), primarily for the UNION operation result storage.
This approach involves using a SQL full outer join to combine the Employees and Salaries tables on the employee_id column. By checking for null values in the resulting join, you can determine which employees have missing information (either name or salary).
In this approach, we establish a connection to the database and use SQLAlchemy to perform a full outer join between the Employees and Salaries tables using their employee IDs. The key here is checking for nulls in both the employee name and salary after the join. We achieve this using the left outer join and union of two conditions: when the name is missing and when the salary is missing. The union ensures all relevant IDs with missing information are captured.
C# (with Entity Framework)
Time Complexity: O(n + m), where n is the number of records in the Employees table and m is the number of records in the Salaries table as we need to check all employees and salaries.
Space Complexity: O(k), where k is the number of employee_ids with missing information, primarily due to the result storage.
This approach involves using two hash maps (dictionaries) to store information about employees and salaries. By comparing the keys of these two maps, we can determine the missing information by finding the employee IDs that are not present in both maps.
This method uses dictionaries to create mappings from Employee IDs to names and salaries, respectively. As we iterate through the IDs in both dictionaries, we identify IDs present in one dictionary but not the other. These IDs are collected to find employees with missing information, and then we sort and return them.
JavaScript
Time Complexity: O(n + m), where n is the size of the employees list and m is the size of the salaries list.
Space Complexity: O(n + m) due to the space used for storing the dictionaries of employees and salaries.
| Approach | Complexity |
|---|---|
| Approach 1: SQL JOIN and NULL Check | Time Complexity: O(N + M), where N is the number of employees and M is the number of salaries, because the join operation requires a scan of both tables. |
| Approach 2: SQL UNION | Time Complexity: O(N * M) since each subquery potentially involves a scan of the Employees table for each entry in Salaries, and vice versa. |
| Approach 1: SQL Full Outer Join | Time Complexity: O(n + m), where n is the number of records in the Employees table and m is the number of records in the Salaries table as we need to check all employees and salaries. |
| Approach 2: Hashing | Time Complexity: O(n + m), where n is the size of the employees list and m is the size of the salaries list. |
Time Needed to Inform All Employees - Leetcode 1376 - Python • NeetCodeIO • 12,877 views views
Watch 9 more video solutions →Practice Employees With Missing Information with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor