Keyboard Row - Solution & Explanation

Problem Overview: You get a list of words and need to return only those that can be typed using letters from a single row of the American keyboard. The three rows are qwertyuiop, asdfghjkl, and zxcvbnm. For each word, verify that every character belongs to the same row.

Approach 1: Using Sets for Each Keyboard Row (O(N) time, O(1) space)

Create three set objects representing the keyboard rows. Iterate through each word in the input array. Convert the word to lowercase, then check whether every character exists in one of the three sets. A simple way is to verify that the set of characters in the word is a subset of a row set. If the condition holds for any row, add the word to the result list.

The key insight is that set lookups run in constant time, so each character check is efficient. The total work is proportional to the number of characters processed across all words. This solution directly models the keyboard layout and keeps the code readable. Time complexity is O(N) where N is the total number of characters across all words, and space complexity is O(1) since the keyboard rows contain a fixed number of letters. This approach heavily relies on fast membership checks using a Hash Table-style structure.

Approach 2: Mapping Characters to Rows (O(N) time, O(1) space)

Instead of storing three sets, build a mapping from each character to its keyboard row index (for example, {'q':1, 'w':1, ..., 'a':2, ..., 'z':3}). For each word, look up the row of the first character. Then iterate through the remaining characters and verify that every character maps to the same row number. If any character belongs to a different row, discard the word.

This approach uses a single hash map for constant-time row lookup. The benefit is that each character comparison becomes a quick integer equality check after the map lookup. It avoids repeated subset checks and is easy to implement in languages like Java or JavaScript. Time complexity remains O(N) because every character is visited once, and space complexity is O(1) since the map stores only 26 lowercase letters.

The input itself is a simple Array of words, and each word is processed character by character as a String. Both approaches scale linearly with the total input size and are efficient for typical interview constraints.

Recommended for interviews: The character-to-row mapping approach is typically what interviewers expect. It shows that you can preprocess a small lookup table and perform a single pass over the input. The set-based solution is equally correct and often shorter to implement, which makes it great for quick coding rounds. Showing both demonstrates that you understand the tradeoff between direct modeling (sets) and optimized lookups (mapping).