Skip to main content

Keyboard Row

Given a list of words, return all the words that require only a single row of a keyboard to type.

Note: You may assume that all words only contain lowercase alphabetical characters.

Example(s)​

Example 1:

Input: words = ["two", "dad", "cat"]
Output: ["two", "dad"]
Explanation:
- "two": All letters (t, w, o) are in the top row ✓
- "dad": All letters (d, a, d) are in the middle row ✓
- "cat": Letters (c, a, t) span multiple rows ✗
  - 'c' is in bottom row
  - 'a' is in middle row
  - 't' is in top row

Example 2:

Input: words = ["ufo", "xzy", "byte"]
Output: []
Explanation:
- "ufo": Letters (u, f, o) span multiple rows ✗
- "xzy": Letters (x, z, y) are all in bottom row, but 'y' is in top row ✗
- "byte": Letters (b, y, t, e) span multiple rows ✗

Example 3:

Input: words = ["qwerty", "asdf", "zxcv"]
Output: ["qwerty", "asdf", "zxcv"]
Explanation:
- "qwerty": All letters in top row ✓
- "asdf": All letters in middle row ✓
- "zxcv": All letters in bottom row ✓

Solution​

The solution uses hash maps to track keyboard rows:

  1. Define rows: Create sets/maps for each keyboard row
  2. Check each word: For each word, check if all characters belong to the same row
  3. Filter words: Return words that can be typed using only one row

JavaScript Solution - Hash Map

/**
* Find words that can be typed using only one keyboard row
* @param {string[]} words - List of words
* @return {string[]} - Words that use only one row
*/
function findWords(words) {
// Define keyboard rows
const topRow = new Set(['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p']);
const middleRow = new Set(['a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l']);
const bottomRow = new Set(['z', 'x', 'c', 'v', 'b', 'n', 'm']);

const result = [];

for (const word of words) {
  if (canTypeInOneRow(word, topRow, middleRow, bottomRow)) {
    result.push(word);
  }
}

return result;
}

/**
* Check if word can be typed using only one row
* @param {string} word - Word to check
* @param {Set} topRow - Top row characters
* @param {Set} middleRow - Middle row characters
* @param {Set} bottomRow - Bottom row characters
* @return {boolean} - True if word uses only one row
*/
function canTypeInOneRow(word, topRow, middleRow, bottomRow) {
if (word.length === 0) return true;

// Determine which row the first character belongs to
const firstChar = word[0].toLowerCase();
let targetRow;

if (topRow.has(firstChar)) {
  targetRow = topRow;
} else if (middleRow.has(firstChar)) {
  targetRow = middleRow;
} else {
  targetRow = bottomRow;
}

// Check if all characters belong to the same row
for (let i = 1; i < word.length; i++) {
  const char = word[i].toLowerCase();
  if (!targetRow.has(char)) {
    return false;
  }
}

return true;
}

// Test cases
console.log('Example 1:', findWords(["two", "dad", "cat"])); 
// ["two", "dad"]

console.log('Example 2:', findWords(["ufo", "xzy", "byte"])); 
// []

console.log('Example 3:', findWords(["qwerty", "asdf", "zxcv"])); 
// ["qwerty", "asdf", "zxcv"]
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Using Map)​

Here's a version using a single map to track row membership:

/**
 * Using a single map to track row membership
 */
function findWordsMap(words) {
  // Create a map: character -> row number
  const rowMap = {};
  
  // Top row: row 0
  'qwertyuiop'.split('').forEach(char => rowMap[char] = 0);
  
  // Middle row: row 1
  'asdfghjkl'.split('').forEach(char => rowMap[char] = 1);
  
  // Bottom row: row 2
  'zxcvbnm'.split('').forEach(char => rowMap[char] = 2);
  
  const result = [];
  
  for (const word of words) {
    if (word.length === 0) {
      result.push(word);
      continue;
    }
    
    const firstRow = rowMap[word[0].toLowerCase()];
    let allSameRow = true;
    
    for (let i = 1; i < word.length; i++) {
      if (rowMap[word[i].toLowerCase()] !== firstRow) {
        allSameRow = false;
        break;
      }
    }
    
    if (allSameRow) {
      result.push(word);
    }
  }
  
  return result;
}

Complexity​

  • Time Complexity: O(n × m) - Where n is the number of words and m is the average length of words. We check each character of each word.
  • Space Complexity: O(1) - The keyboard row sets/maps are constant size (26 characters).

Approach​

The solution uses hash maps/sets to track keyboard rows:

  1. Define keyboard rows:

    • Top row: qwertyuiop
    • Middle row: asdfghjkl
    • Bottom row: zxcvbnm

  2. Check each word:

    • Determine which row the first character belongs to
    • Check if all remaining characters belong to the same row

  3. Filter words:

    • Add words to result if all characters are in the same row
    • Return the filtered list

Key Insights​

  • Three rows: QWERTY keyboard has three rows
  • First character determines row: Use first character to determine target row
  • Check all characters: All characters must belong to the same row
  • Case insensitive: Convert to lowercase for comparison
  • O(n×m) time: Must check each character of each word

Step-by-Step Example​

Let's trace through Example 1: words = ["two", "dad", "cat"]

Word 1: "two"
  First char: 't' → belongs to top row
  Check 'w': in top row? Yes ✓
  Check 'o': in top row? Yes ✓
  Result: "two" uses only one row ✓

Word 2: "dad"
  First char: 'd' → belongs to middle row
  Check 'a': in middle row? Yes ✓
  Check 'd': in middle row? Yes ✓
  Result: "dad" uses only one row ✓

Word 3: "cat"
  First char: 'c' → belongs to bottom row
  Check 'a': in bottom row? No (in middle row) ✗
  Result: "cat" uses multiple rows ✗

Final: ["two", "dad"]

Visual Representation​

QWERTY Keyboard Rows:

Top row:    q w e r t y u i o p
Middle row: a s d f g h j k l
Bottom row: z x c v b n m

Example 1: words = ["two", "dad", "cat"]

"two":
  t → top row
  w → top row
  o → top row
  All in top row ✓

"dad":
  d → middle row
  a → middle row
  d → middle row
  All in middle row ✓

"cat":
  c → bottom row
  a → middle row ✗
  t → top row ✗
  Multiple rows ✗

Edge Cases​

  • Empty word: Return empty word (can be typed with one row)
  • Single character: Always returns true
  • All same character: Returns true
  • Empty list: Returns empty list
  • Mixed case: Convert to lowercase for comparison

Important Notes​

  • QWERTY layout: Standard keyboard layout
  • Case insensitive: Problem states lowercase, but handle case conversion
  • All characters same row: Every character must be in the same row
  • First character determines row: Use first char to identify target row
  • O(n×m) time: Check each character of each word

Keyboard Row Layout​

Standard QWERTY Keyboard:

Top row:    Q W E R T Y U I O P
Middle row: A S D F G H J K L
Bottom row: Z X C V B N M

Note: The problem uses lowercase, but the layout is the same.

  • Valid Anagram: Different string problem
  • Group Anagrams: Different grouping problem
  • Isomorphic Strings: Different string problem
  • Word Pattern: Different pattern matching

Takeaways​

  • Hash maps/sets efficiently check row membership
  • First character determines which row to check
  • All characters must belong to the same row
  • O(n×m) time to check all words
  • O(1) space for keyboard row data structures