Fix Names in a Table - Solution & Explanation
Problem Statement
Table: Users
+----------------+---------+ | Column Name | Type | +----------------+---------+ | user_id | int | | name | varchar | +----------------+---------+ user_id is the primary key (column with unique values) for this table. This table contains the ID and the name of the user. The name consists of only lowercase and uppercase characters.
Write a solution to fix the names so that only the first character is uppercase and the rest are lowercase.
Return the result table ordered by user_id.
The result format is in the following example.
Example 1:
Input: Users table: +---------+-------+ | user_id | name | +---------+-------+ | 1 | aLice | | 2 | bOB | +---------+-------+ Output: +---------+-------+ | user_id | name | +---------+-------+ | 1 | Alice | | 2 | Bob | +---------+-------+
Approach Overview
Problem Overview: The table contains user names with inconsistent capitalization. The task is to normalize each name so the first character is uppercase and all remaining characters are lowercase, then return the result ordered by user_id. This is primarily a string normalization problem often solved with built-in string functions in database queries or basic iteration in programming languages.
Approach 1: Use Loop to Transform Each Name (Time: O(n · m), Space: O(m))
Iterate through each name and rebuild it with the correct capitalization. Extract the first character, convert it using toUpperCase() or an equivalent function, and convert the remaining substring using toLowerCase(). Concatenate the two parts to form the normalized name. Here, n is the number of rows and m is the average length of a name. This approach mirrors how you would solve the problem in languages like C++, Java, Python, or JavaScript by iterating through strings and applying simple string operations. In SQL-based solutions, the same idea appears as UPPER(SUBSTRING(name,1,1)) combined with LOWER(SUBSTRING(name,2)).
The key insight is that only the first character needs special handling. Once separated, the remaining substring can be normalized with a single lowercase transformation. The algorithm scans each character at most once per name, making it efficient for large tables.
Approach 2: Use Regex Replacement Method (Time: O(n · m), Space: O(m))
Regular expressions provide a compact way to normalize names. A regex pattern captures the first character separately from the rest of the string. The replacement function then uppercases the first capture group and lowercases the second. Languages like Python and JavaScript support regex callbacks, allowing you to transform matched groups dynamically. This approach still processes each character once, so the time complexity remains proportional to the total length of all names.
Regex solutions are concise and expressive when you already rely on regex utilities in your codebase. However, they introduce slightly more overhead and are sometimes harder to read compared to direct substring manipulation.
Recommended for interviews: The loop or substring-based transformation is the expected solution. It clearly shows you understand string manipulation and built-in case conversion functions. Regex works as an alternative but is rarely necessary unless the formatting rules become more complex.
Approach 1: Approach 1: Use Loop to Transform Each Name
This approach involves iterating through each name in the list, transforming the name so that the first letter is uppercase and the rest are lowercase. This is a common string manipulation problem that can be solved using built-in string functions in most programming languages.
In C, we use the toupper and tolower functions from ctype.h to modify the casing of each character in the string. The first character is capitalized, while the rest are converted to lowercase.
Complexity
Time Complexity: O(n) for each name, where n is the length of the name.
Space Complexity: O(1) since we modify the names in place.
Approach 2: Approach 2: Use Regex Replacement Method
This approach applies regular expressions to locate patterns that match the criteria and replace them with the desired format. This leverages the pattern matching capability of regex to achieve the transformation in fewer lines of code.
In this Python solution, the regex (\w)(\w*) captures the first character and the remainder of the string separately. The lambda function then applies the uppercase and lowercase transformations in one substitution step.
Code
Python
JavaScript
Complexity
Time Complexity: O(n) for each name due to regex matching and replacement, where n is the length of the name.
Space Complexity: O(n) for storing the modified strings.
Approach 3: Default Approach
Code
MySQL
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Use Loop to Transform Each Name | Time Complexity: O(n) for each name, where n is the length of the name. |
| Approach 2: Use Regex Replacement Method | Time Complexity: O(n) for each name due to regex matching and replacement, where n is the length of the name. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Loop to Transform Each Name | O(n · m) | O(m) | General case. Clear and readable solution using substring and case conversion functions. |
| Regex Replacement Method | O(n · m) | O(m) | Useful when regex utilities are already used or when string formatting rules become more complex. |
Video Solution
Fix Names in a Table | Leetcode 1667 | Crack SQL Interviews in 50 Qs #mysql #leetcode • Learn With Chirag • 5,816 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Fix Names in a Table easy or hard?
Fix Names in a Table Python/Java solution
How to solve Fix Names in a Table in O(n)?
What is the best approach for Fix Names in a Table?
Is Fix Names in a Table asked at Google/Amazon/Meta?
What data structure is used in Fix Names in a Table?
What is the time complexity of Fix Names in a Table?
Ready to solve this problem?
Practice Fix Names in a Table with our built-in code editor and test cases.
Practice on FleetCode