Making File Names Unique - Video Solutions

Problem Overview: You receive a list of folder or file names. When a name already exists, the system must create a new unique name by appending a suffix like (k) where k is the smallest positive integer that keeps the name unique. The goal is to process the list and return the final unique names while preserving order.

Approach 1: HashMap to Track Folder Names (O(n) average time, O(n) space)

This approach uses a hash map to track previously used names and the next available suffix for each base name. Iterate through the input array once. If the current name has not been seen, store it in the map with suffix index 1. If it already exists, repeatedly generate names like name(k) and check the map until a free one appears. Store both the generated name and the updated suffix index in the map so future collisions skip directly to the next candidate. Hash lookups make each check O(1) on average, giving near O(n) total time.

The key insight is remembering the next suffix for each base name. Without this optimization, you'd repeatedly test (1), (2), (3) even if those suffixes were already used. Tracking the next candidate prevents unnecessary retries. This method relies heavily on a hash table for constant-time lookups and works well with sequential iteration of the array.

Approach 2: Two-pass Approach with Back-Checking (O(n * k) worst case, O(n) space)

The two-pass strategy first records all names encountered, then resolves duplicates by checking suffix variations when collisions occur. During iteration, if a name already exists, incrementally test name(1), name(2), and so on until an unused name is found. Each candidate requires a lookup in a hash structure that stores all assigned names.

This approach is simpler conceptually but can degrade in worst-case scenarios when many duplicates appear. For example, if a name repeats hundreds of times, the algorithm may repeatedly check many suffix values. Each lookup is still constant time using a string key in a hash set, but the repeated suffix generation increases total work.

Recommended for interviews: The HashMap suffix-tracking approach is the expected solution. It demonstrates efficient state tracking and avoids redundant work by remembering the next valid suffix for every base name. Interviewers usually accept the simpler back-checking method first, but optimizing it with suffix pointers shows stronger algorithmic thinking and understanding of hash-based indexing.