1667. Fix Names in a Table Solution

The problem

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.

Python

def format_names(users):
    return [(user_id, name.capitalize()) for user_id, name in users]

# Example usage
users = [(1, "aLice"), (2, "bOB")]
formatted_users = format_names(users)

print("+---------+-------+")
print("| user_id | name  |")
print("+---------+-------+")
for user_id, name in formatted_users:
    print(f"| {user_id}       | {name} |")
print("+---------+-------+")

Java

import java.util.Arrays;
import java.util.List;

public class Main {
    public static void formatName(String[] names) {
        for (int i = 0; i < names.length; i++) {
            if (names[i].length() == 0) continue;
            String formattedName = names[i].substring(0, 1).toUpperCase() + names[i].substring(1).toLowerCase();
            names[i] = formattedName;
        }
    }

    public static void main(String[] args) {
        String[] names = {"aLice", "bOB"};
        int[] user_ids = {1, 2};

        formatName(names);
        System.out.println("+---------+-------+");
        System.out.println("| user_id | name  |");
        System.out.println("+---------+-------+");
        for (int i = 0; i < user_ids.length; i++) {
            System.out.format("| %d       | %s |\n", user_ids[i], names[i]);
        }
        System.out.println("+---------+-------+");
    }
}

C++

#include <iostream>
#include <algorithm>
#include <cctype>
#include <vector>

void formatName(std::string &name) {
    if (name.empty()) return;
    name[0] = toupper(name[0]);
    std::transform(name.begin() + 1, name.end(), name.begin() + 1, ::tolower);
}

int main() {
    // Example usage
    std::vector<std::pair<int, std::string>> users = {{1, "aLice"}, {2, "bOB"}};
    
    std::cout << "+---------+-------+\n";
    std::cout << "| user_id | name  |\n";
    std::cout << "+---------+-------+\n";
    for (auto &user : users) {
        formatName(user.second);
        std::cout << "| " << user.first << "       | " << user.second << " |\n";
    }
    std::cout << "+---------+-------+\n";

    return 0;
}

JavaScript

function formatNames(users) {
    return users.map(([userId, name]) => [userId, name.charAt(0).toUpperCase() + name.slice(1).toLowerCase()]);
}

// Example usage
const users = [[1, 'aLice'], [2, 'bOB']];
const formattedUsers = formatNames(users);

console.log("+---------+-------+");
console.log("| user_id | name  |");
console.log("+---------+-------+");
formattedUsers.forEach(([userId, name]) => {
    console.log(`| ${userId}       | ${name} |`);
});
console.log("+---------+-------+");

#include <stdio.h>
#include <ctype.h>
#include <string.h>

void formatName(char *name) {
    if (strlen(name) == 0) return;
    name[0] = toupper(name[0]);
    for (int i = 1; name[i] != '\0'; i++) {
        name[i] = tolower(name[i]);
    }
}

int main() {
    // Example usage
    char names[][20] = {"aLice", "bOB"};
    int user_ids[] = {1, 2};
    int n = sizeof(user_ids) / sizeof(user_ids[0]);

    printf("+---------+-------+\n");
    printf("| user_id | name  |\n");
    printf("+---------+-------+\n");
    for (int i = 0; i < n; i++) {
        formatName(names[i]);
        printf("| %d       | %s |\n", user_ids[i], names[i]);
    }
    printf("+---------+-------+\n");

    return 0;
}

using System;
using System.Collections.Generic;

class Program {
    public static void FormatNames(List<Tuple<int, string>> users) {
        for (int i = 0; i < users.Count; i++) {
            string name = users[i].Item2;
            if (!string.IsNullOrEmpty(name)) {
                name = char.ToUpper(name[0]) + name.Substring(1).ToLower();
                users[i] = new Tuple<int, string>(users[i].Item1, name);
            }
        }
    }

    public static void Main(string[] args) {
        var users = new List<Tuple<int, string>> {
            Tuple.Create(1, "aLice"),
            Tuple.Create(2, "bOB")
        };

        FormatNames(users);
        Console.WriteLine("+---------+-------+");
        Console.WriteLine("| user_id | name  |");
        Console.WriteLine("+---------+-------+");
        foreach (var user in users) {
            Console.WriteLine($"| {user.Item1}       | {user.Item2} |");
        }
        Console.WriteLine("+---------+-------+");
    }
}

Python's str.capitalize() method is used directly to ensure the first character is uppercase and the rest are lowercase. A list comprehension helps apply this operation to each name.

Complexity

Time Complexity: O(n) for each name, where n is the length of the name.
Space Complexity: O(n) for storing the modified list of names.

Try this approach in the editor

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.

Python

import re

def format_names(users):
    return [(user_id, re.sub(r'(\w)(\w*)', lambda m: m.group(1).upper() + m.group(2).lower(), name)) for user_id, name in users]

# Example usage
users = [(1, "aLice"), (2, "bOB")]
formatted_users = format_names(users)

print("+---------+-------+")
print("| user_id | name  |")
print("+---------+-------+")
for user_id, name in formatted_users:
    print(f"| {user_id}       | {name} |")
print("+---------+-------+")

JavaScript

function formatNames(users) {
    return users.map(([userId, name]) => [userId, name.replace(/^(\w)(\w*)/, (_, first, rest) => first.toUpperCase() + rest.toLowerCase())]);
}

// Example usage
const users = [[1, 'aLice'], [2, 'bOB']];
const formattedUsers = formatNames(users);

console.log("+---------+-------+");
console.log("| user_id | name  |");
console.log("+---------+-------+");
formattedUsers.forEach(([userId, name]) => {
    console.log(`| ${userId}       | ${name} |`);
});
console.log("+---------+-------+");

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.

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.

Try this approach in the editor

Approach 3: Default Approach

MySQL

SELECT
    user_id,
    CONCAT(UPPER(LEFT(name, 1)), LOWER(SUBSTRING(name, 2))) AS name
FROM
    users
ORDER BY
    user_id;

Try this approach in the editor

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. Space Complexity: O(n) for storing the modified list of names.
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. Space Complexity: O(n) for storing the modified strings.
Default Approach	–

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.

Frequently asked questions

Is Fix Names in a Table easy or hard?

Fix Names in a Table is classified as an Easy problem. The challenge focuses on correct string formatting rather than complex algorithms, making it a common introductory database or string manipulation exercise.

Fix Names in a Table Python/Java solution

In Python or Java, take the first character of the string, apply upper() or toUpperCase(), then append the remainder converted with lower() or toLowerCase(). SQL implementations follow the same logic using UPPER(SUBSTRING(name,1,1)) combined with LOWER(SUBSTRING(name,2)).

How to solve Fix Names in a Table in O(n)?

Treat n as the number of rows and apply a constant number of string operations per row. Extract the first character, convert it to uppercase, convert the remaining substring to lowercase, and concatenate them. Although each string operation touches the characters, the algorithm scales linearly with the dataset size.

What is the best approach for Fix Names in a Table?

The most practical solution is to separate the first character and the remaining substring, convert the first to uppercase and the rest to lowercase, then concatenate them. In SQL this is typically implemented using UPPER and LOWER with SUBSTRING. The approach runs in O(n · m) time where n is the number of rows and m is the average name length.

Is Fix Names in a Table asked at Google/Amazon/Meta?

This problem reflects common data-cleaning tasks frequently discussed in SQL and database interviews. Variations of string normalization and formatting appear in interview question sets used by large companies such as Amazon and Google when evaluating SQL proficiency.

What data structure is used in Fix Names in a Table?

No complex data structure is required. The solution relies on basic string manipulation functions provided by the programming language or SQL engine, such as substring extraction and case conversion operations.

What is the time complexity of Fix Names in a Table?

The time complexity is O(n · m). Each of the n names is processed once, and each transformation scans the characters of the name whose average length is m. Space complexity is O(m) because a normalized string is created for each name.

Fix Names in a Table solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Use Loop to Transform Each Name

Approach 2: Approach 2: Use Regex Replacement Method

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Fix Names in a Table solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Use Loop to Transform Each Name

Approach 2: Approach 2: Use Regex Replacement Method

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems