Facebook Pixel

2071. Maximum Number of Tasks You Can Assign

HardGreedyQueueArrayTwo PointersBinary SearchSortingMonotonic Queue
Leetcode Link

Problem Description

You have n tasks and m workers. Each task requires a certain strength to complete, stored in array tasks, where tasks[i] is the strength needed for the i-th task. Each worker has a strength value stored in array workers, where workers[j] is the strength of the j-th worker.

To complete a task, a worker must have strength greater than or equal to the task's requirement. Each worker can only be assigned to one task at most.

You also have a limited number of magical pills (given by pills). Each pill increases a worker's strength by exactly strength points. Each worker can take at most one pill.

The goal is to find the maximum number of tasks that can be completed by optimally:

  • Assigning workers to tasks (each worker can do at most one task)
  • Distributing pills to workers (each worker can take at most one pill)

For example, if you have:

  • tasks = [3, 2, 1] (three tasks requiring strengths 3, 2, and 1)
  • workers = [0, 3, 3] (three workers with strengths 0, 3, and 3)
  • pills = 1 (one pill available)
  • strength = 1 (each pill increases strength by 1)

You could give the pill to the first worker (strength becomes 0+1=1), allowing them to complete the task requiring strength 1. The other two workers with strength 3 can complete the tasks requiring strengths 2 and 3. Thus, all 3 tasks can be completed.

The function should return the maximum number of tasks that can be completed given these constraints.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that if we can complete x tasks, then we can definitely complete x-1, x-2, ..., 1, or 0 tasks. This monotonic property suggests we can use binary search to find the maximum number of tasks we can complete.

First, let's sort both arrays. Sorting tasks in ascending order and workers in ascending order helps us make greedy decisions. When trying to complete x tasks, we should:

  • Use the easiest x tasks (the first x tasks after sorting)
  • Use the strongest x workers (the last x workers after sorting)

This gives us the best chance of success because we're matching the easiest tasks with our strongest workers.

For the greedy strategy within each check: when we iterate through our selected workers from weakest to strongest, each worker should consider all tasks they could potentially complete (with or without a pill). Among these available tasks:

  • If the worker can complete the easiest task without a pill, do it without using a pill (save pills for workers who really need them)
  • If the worker needs a pill to complete any task, use the pill to complete the hardest possible task (this maximizes the value we get from the pill)

Why does this greedy approach work? Consider a worker who needs a pill. If we use the pill on this worker to complete an easier task when they could complete a harder one, we might later find that another worker can't complete that harder task even with a pill. By having each worker who uses a pill complete the hardest task they can, we leave easier tasks for subsequent workers who might be able to complete them without pills or with less "waste" of pill strength.

The deque structure helps efficiently track which tasks are available for the current worker - we can add newly available tasks to the back and remove completed tasks from either end depending on whether we used a pill or not.

Learn more about Greedy, Queue, Two Pointers, Binary Search, Sorting and Monotonic Queue patterns.

Solution Implementation

1class Solution:
2    def maxTaskAssign(
3        self, tasks: List[int], workers: List[int], pills: int, strength: int
4    ) -> int:
5        def feasible(k: int) -> bool:
6            """
7            Check if we can assign k tasks to the strongest k workers.
8
9            Strategy: Use the strongest k workers and try to complete the easiest k tasks.
10            For each worker (from weakest to strongest among the selected k):
11            - Add all tasks that this worker could complete with a pill to the queue
12            - If worker can complete the easiest task without pill, do it
13            - Otherwise, use a pill on the hardest task in queue (greedy choice)
14            """
15            task_index = 0
16            available_tasks = deque()
17            pills_remaining = pills
18
19            # Iterate through the strongest k workers (from weakest to strongest)
20            for worker_index in range(num_workers - k, num_workers):
21                current_worker_strength = workers[worker_index]
22
23                # Add all tasks that this worker could potentially complete (with pill)
24                # to the available tasks queue
25                while task_index < k and tasks[task_index] <= current_worker_strength + strength:
26                    available_tasks.append(tasks[task_index])
27                    task_index += 1
28
29                # No tasks available for this worker
30                if not available_tasks:
31                    return False
32
33                # If worker can complete the easiest task without a pill
34                if available_tasks[0] <= current_worker_strength:
35                    available_tasks.popleft()
36                # Need a pill but none available
37                elif pills_remaining == 0:
38                    return False
39                # Use a pill on the hardest available task
40                else:
41                    pills_remaining -= 1
42                    available_tasks.pop()  # Remove the hardest task from the right
43
44            return True
45
46        # Initialize variables
47        num_tasks = len(tasks)
48        num_workers = len(workers)
49
50        # Sort both arrays for greedy assignment
51        tasks.sort()
52        workers.sort()
53
54        # Binary search for the maximum number of tasks we can complete
55        # feasible(k) creates pattern: [true, true, ..., false, false]
56        # We want the last true (maximum k where we can complete tasks)
57        # Invert: not_feasible(k) creates pattern: [false, false, ..., true, true]
58        # Find first_true_index of not_feasible, answer is first_true_index - 1
59        left, right = 0, min(num_tasks, num_workers)
60        first_true_index = -1
61
62        while left <= right:
63            mid = (left + right) // 2
64            if not feasible(mid):  # not_feasible condition
65                first_true_index = mid
66                right = mid - 1
67            else:
68                left = mid + 1
69
70        # If first_true_index == -1, all values are feasible, return max
71        # If first_true_index == 0, even 0 tasks is not feasible (shouldn't happen)
72        # Otherwise, return first_true_index - 1 (last feasible value)
73        if first_true_index == -1:
74            return min(num_tasks, num_workers)
75        return first_true_index - 1 if first_true_index > 0 else 0
76
1class Solution {
2    // Instance variables to store problem parameters
3    private int[] tasks;
4    private int[] workers;
5    private int strength;
6    private int pills;
7    private int tasksLength;
8    private int workersLength;
9
10    /**
11     * Finds the maximum number of tasks that can be completed by workers.
12     * Workers can optionally take pills to increase their strength.
13     *
14     * @param tasks Array of task difficulties
15     * @param workers Array of worker strengths
16     * @param pills Number of available strength-enhancing pills
17     * @param strength Amount of strength increase from each pill
18     * @return Maximum number of tasks that can be completed
19     */
20    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
21        // Sort both arrays to enable efficient matching
22        Arrays.sort(tasks);
23        Arrays.sort(workers);
24
25        // Initialize instance variables
26        this.tasks = tasks;
27        this.workers = workers;
28        this.strength = strength;
29        this.pills = pills;
30        this.tasksLength = tasks.length;
31        this.workersLength = workers.length;
32
33        // Binary search for the maximum number of tasks that can be completed
34        // feasible(k) creates pattern: [true, true, ..., false, false]
35        // Invert: not_feasible(k) creates pattern: [false, false, ..., true, true]
36        // Find first_true_index of not_feasible, answer is first_true_index - 1
37        int left = 0;
38        int right = Math.min(workersLength, tasksLength);
39        int firstTrueIndex = -1;
40
41        while (left <= right) {
42            int mid = left + (right - left) / 2;
43            if (!feasible(mid)) {  // not_feasible condition
44                firstTrueIndex = mid;
45                right = mid - 1;
46            } else {
47                left = mid + 1;
48            }
49        }
50
51        // If firstTrueIndex == -1, all values are feasible, return max
52        // Otherwise, return firstTrueIndex - 1 (last feasible value)
53        if (firstTrueIndex == -1) {
54            return Math.min(workersLength, tasksLength);
55        }
56        return firstTrueIndex > 0 ? firstTrueIndex - 1 : 0;
57    }
58
59    /**
60     * Checks if it's possible to complete exactly k tasks.
61     * Uses a greedy approach: assign strongest k workers to easiest k tasks.
62     *
63     * @param k Number of tasks to attempt completing
64     * @return true if k tasks can be completed, false otherwise
65     */
66    private boolean feasible(int k) {
67        int taskIndex = 0;
68        Deque<Integer> availableTasks = new ArrayDeque<>();
69        int remainingPills = pills;
70
71        // Iterate through the k strongest workers (from right side of sorted array)
72        for (int workerIndex = workersLength - k; workerIndex < workersLength; workerIndex++) {
73            // Add all tasks that this worker could complete with a pill
74            // to the available tasks queue
75            while (taskIndex < k && tasks[taskIndex] <= workers[workerIndex] + strength) {
76                availableTasks.offer(tasks[taskIndex]);
77                taskIndex++;
78            }
79
80            // If no tasks are available for this worker, assignment fails
81            if (availableTasks.isEmpty()) {
82                return false;
83            }
84
85            // Try to assign the easiest task without using a pill
86            if (availableTasks.peekFirst() <= workers[workerIndex]) {
87                availableTasks.pollFirst();
88            }
89            // If the easiest task requires a pill, check if pills are available
90            else if (remainingPills == 0) {
91                return false;
92            }
93            // Use a pill and assign the hardest available task
94            // (greedy: save easier tasks for weaker workers)
95            else {
96                remainingPills--;
97                availableTasks.pollLast();
98            }
99        }
100
101        return true;
102    }
103}
104
1class Solution {
2public:
3    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
4        // Sort both arrays to enable greedy assignment
5        sort(tasks.begin(), tasks.end());
6        sort(workers.begin(), workers.end());
7
8        int numTasks = tasks.size();
9        int numWorkers = workers.size();
10
11        // Lambda function to check if we can complete 'targetTasks' number of tasks
12        auto feasible = [&](int targetTasks) -> bool {
13            int remainingPills = pills;
14            deque<int> availableTasks;  // Tasks that can potentially be done (with or without pill)
15            int taskIndex = 0;
16
17            // Try to assign the strongest workers to complete targetTasks
18            // Start from the strongest workers (last targetTasks workers)
19            for (int workerIndex = numWorkers - targetTasks; workerIndex < numWorkers; ++workerIndex) {
20                // Add all tasks that this worker can do with a pill to the deque
21                while (taskIndex < targetTasks && tasks[taskIndex] <= workers[workerIndex] + strength) {
22                    availableTasks.push_back(tasks[taskIndex]);
23                    taskIndex++;
24                }
25
26                // If no tasks available for this worker, assignment fails
27                if (availableTasks.empty()) {
28                    return false;
29                }
30
31                // Try to assign the easiest task without using a pill
32                if (availableTasks.front() <= workers[workerIndex]) {
33                    availableTasks.pop_front();
34                }
35                // Otherwise, use a pill to complete the hardest available task
36                else if (remainingPills == 0) {
37                    return false;  // No pills left, cannot complete assignment
38                }
39                else {
40                    remainingPills--;
41                    availableTasks.pop_back();  // Remove the hardest task (requires pill)
42                }
43            }
44
45            return true;
46        };
47
48        // Binary search for the maximum number of tasks that can be completed
49        // feasible(k) creates pattern: [true, true, ..., false, false]
50        // Invert: not_feasible(k) creates pattern: [false, false, ..., true, true]
51        // Find first_true_index of not_feasible, answer is first_true_index - 1
52        int left = 0;
53        int right = min(numWorkers, numTasks);
54        int firstTrueIndex = -1;
55
56        while (left <= right) {
57            int mid = left + (right - left) / 2;
58            if (!feasible(mid)) {  // not_feasible condition
59                firstTrueIndex = mid;
60                right = mid - 1;
61            } else {
62                left = mid + 1;
63            }
64        }
65
66        // If firstTrueIndex == -1, all values are feasible, return max
67        // Otherwise, return firstTrueIndex - 1 (last feasible value)
68        if (firstTrueIndex == -1) {
69            return min(numWorkers, numTasks);
70        }
71        return firstTrueIndex > 0 ? firstTrueIndex - 1 : 0;
72    }
73};
74
1/**
2 * Assigns maximum number of tasks to workers with optional strength pills
3 * @param tasks - Array of task difficulties
4 * @param workers - Array of worker strengths
5 * @param pills - Number of strength pills available
6 * @param strength - Strength boost provided by each pill
7 * @returns Maximum number of tasks that can be completed
8 */
9function maxTaskAssign(
10    tasks: number[],
11    workers: number[],
12    pills: number,
13    strength: number,
14): number {
15    // Sort both arrays in ascending order
16    tasks.sort((a, b) => a - b);
17    workers.sort((a, b) => a - b);
18
19    const tasksCount = tasks.length;
20    const workersCount = workers.length;
21
22    /**
23     * Checks if it's possible to complete 'targetTasks' number of tasks
24     * @param targetTasks - Number of tasks to attempt completing
25     * @returns true if targetTasks can be completed, false otherwise
26     */
27    const feasible = (targetTasks: number): boolean => {
28        // Deque to store assignable tasks for current configuration
29        const taskDeque = new Array<number>(targetTasks);
30        let dequeHead = 0;
31        let dequeTail = 0;
32
33        // Deque helper functions
34        const isEmpty = (): boolean => dequeHead === dequeTail;
35        const pushBack = (value: number): void => {
36            taskDeque[dequeTail++] = value;
37        };
38        const popFront = (): void => {
39            dequeHead++;
40        };
41        const popBack = (): void => {
42            dequeTail--;
43        };
44        const getFront = (): number => taskDeque[dequeHead];
45
46        let taskIndex = 0;
47        let remainingPills = pills;
48
49        // Try to assign tasks to the strongest 'targetTasks' workers
50        for (let workerIndex = workersCount - targetTasks; workerIndex < workersCount; workerIndex++) {
51            // Add all tasks that this worker could potentially complete (with pill)
52            while (taskIndex < targetTasks && tasks[taskIndex] <= workers[workerIndex] + strength) {
53                pushBack(tasks[taskIndex]);
54                taskIndex++;
55            }
56
57            // No assignable tasks for this worker
58            if (isEmpty()) {
59                return false;
60            }
61
62            // Check if worker can complete the easiest available task without pill
63            if (getFront() <= workers[workerIndex]) {
64                // Assign easiest task without using a pill
65                popFront();
66            } else {
67                // Worker needs a pill to complete any task
68                if (remainingPills === 0) {
69                    return false;
70                }
71                // Use a pill and assign the hardest possible task
72                remainingPills--;
73                popBack();
74            }
75        }
76
77        return true;
78    };
79
80    // Binary search for the maximum number of tasks that can be completed
81    // feasible(k) creates pattern: [true, true, ..., false, false]
82    // Invert: not_feasible(k) creates pattern: [false, false, ..., true, true]
83    // Find first_true_index of not_feasible, answer is first_true_index - 1
84    let left: number = 0;
85    let right: number = Math.min(tasksCount, workersCount);
86    let firstTrueIndex: number = -1;
87
88    while (left <= right) {
89        const mid: number = Math.floor((left + right) / 2);
90        if (!feasible(mid)) {  // not_feasible condition
91            firstTrueIndex = mid;
92            right = mid - 1;
93        } else {
94            left = mid + 1;
95        }
96    }
97
98    // If firstTrueIndex == -1, all values are feasible, return max
99    // Otherwise, return firstTrueIndex - 1 (last feasible value)
100    if (firstTrueIndex === -1) {
101        return Math.min(tasksCount, workersCount);
102    }
103    return firstTrueIndex > 0 ? firstTrueIndex - 1 : 0;
104}
105

Solution Approach

The solution uses binary search combined with a greedy assignment strategy.

Step 1: Sorting

tasks.sort()
workers.sort()

Sort both arrays in ascending order to enable greedy decisions.

Step 2: Binary Search Setup

left, right = 0, min(n, m)

We can complete at most min(n, m) tasks (limited by either the number of tasks or workers). Binary search finds the maximum number of tasks we can complete.

Step 3: Binary Search Loop

while left < right:
    mid = (left + right + 1) >> 1
    if check(mid):
        left = mid
    else:
        right = mid - 1

If we can complete mid tasks, try a larger number. Otherwise, try a smaller number.

Step 4: The check(x) Function

This function determines if we can complete exactly x tasks using a greedy strategy:

def check(x):
    i = 0
    q = deque()
    p = pills
    for j in range(m - x, m):
  • Use the strongest x workers: workers[m-x] to workers[m-1]
  • Process workers from weakest to strongest among these selected workers
  • i tracks the next task to consider
  • q is a deque storing currently available tasks for worker j
  • p tracks remaining pills

For each worker j:

while i < x and tasks[i] <= workers[j] + strength:
    q.append(tasks[i])
    i += 1

Add all tasks that this worker could potentially complete (with a pill) to the deque.

if not q:
    return False

If no tasks are available for this worker, it's impossible to complete x tasks.

if q[0] <= workers[j]:
    q.popleft()

If the worker can complete the easiest available task without a pill, do so. Remove from the front of the deque (smallest task).

elif p == 0:
    return False
else:
    p -= 1
    q.pop()

Otherwise, the worker needs a pill. If no pills remain, return false. If pills are available, use one and complete the hardest available task (remove from the back of the deque).

The greedy logic ensures:

  • Workers who don't need pills complete easier tasks
  • Workers who need pills complete harder tasks to maximize pill value
  • Pills are used only when necessary

The algorithm runs in O((n + m) log(min(n, m)) * min(n, m)) time complexity due to the binary search and the linear check function.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to understand how the algorithm works:

Given:

  • tasks = [5, 9, 8, 5, 9]
  • workers = [1, 6, 4, 2, 6]
  • pills = 1
  • strength = 5

Step 1: Sort both arrays

  • tasks = [5, 5, 8, 9, 9]
  • workers = [1, 2, 4, 6, 6]

Step 2: Binary Search We can complete at most min(5, 5) = 5 tasks. Binary search range: [0, 5]

First iteration: mid = 3 (check if we can complete 3 tasks)

  • Select easiest 3 tasks: [5, 5, 8]
  • Select strongest 3 workers: [4, 6, 6]

Processing workers from weakest to strongest:

  • Worker with strength 4:

    • Can potentially complete tasks [5, 5, 8] with pill (4+5=9)
    • Add all to deque: q = [5, 5, 8]
    • Can't complete task 5 without pill (4 < 5)
    • Use pill → strength becomes 9 → complete hardest task (8)
    • Remove 8 from back: q = [5, 5], pills = 0

  • Worker with strength 6:

    • No new tasks to add (all were already added)
    • q = [5, 5]
    • Can complete task 5 without pill (6 ≥ 5)
    • Remove 5 from front: q = [5]

  • Worker with strength 6:

    • No new tasks to add
    • q = [5]
    • Can complete task 5 without pill (6 ≥ 5)
    • Remove 5 from front: q = []

✓ Successfully completed 3 tasks! Update: left = 3

Second iteration: mid = 4 (check if we can complete 4 tasks)

  • Select easiest 4 tasks: [5, 5, 8, 9]
  • Select strongest 4 workers: [2, 4, 6, 6]

Processing workers:

  • Worker with strength 2:

    • Can potentially complete tasks [5, 5] with pill (2+5=7)
    • Add to deque: q = [5, 5]
    • Can't complete task 5 without pill (2 < 5)
    • Use pill → strength becomes 7 → complete hardest task (5)
    • Remove 5 from back: q = [5], pills = 0

  • Worker with strength 4:

    • Can potentially complete task [8] with pill (4+5=9)
    • Add to deque: q = [5, 8]
    • Can't complete task 5 without pill (4 < 5)
    • Need pill but pills = 0 → Return False

✗ Cannot complete 4 tasks! Update: right = 3

Binary search converges: left = right = 3

Answer: 3 tasks can be completed

The key insight illustrated here is how the greedy strategy works:

  1. When the worker with strength 4 used the pill in the 3-task scenario, they wisely chose the hardest task (8), leaving easier tasks for stronger workers
  2. This allowed the two workers with strength 6 to complete the remaining tasks without pills
  3. When we tried 4 tasks, we ran out of pills too early because weaker workers needed them, demonstrating why the greedy pill usage (complete hardest possible task when using a pill) is optimal

Time and Space Complexity

Time Complexity: O((n + m) × log(n + m) + min(n, m) × n × log(min(n, m)))

The time complexity breaks down as follows:

  • Sorting tasks array: O(n × log n) where n is the number of tasks
  • Sorting workers array: O(m × log m) where m is the number of workers
  • Binary search runs O(log(min(n, m))) iterations
  • For each binary search iteration, the check function is called:
    • The outer loop in check runs x times (at most min(n, m))
    • The inner while loop processes at most x tasks total across all iterations
    • Deque operations (append, popleft, pop) are O(1)
    • Overall check function: O(x) where x ≤ min(n, m)
  • Total for binary search with check: O(min(n, m) × log(min(n, m)))

Since sorting dominates when n and m are large, and considering the reference answer simplifies to O(n × log n), this suggests m is treated as comparable to n. The dominant term becomes O(n × log n).

Space Complexity: O(n)

The space complexity consists of:

  • The deque q in the check function can hold at most x elements, where x ≤ min(n, m) ≤ n
  • Other variables use constant space
  • Total space: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

This problem finds the maximum (last true) rather than minimum (first true). The correct approach inverts the condition to use the standard first-true template.

Incorrect Implementation:

# WRONG: Using while left < right with ceiling division
while left < right:
    mid = (left + right + 1) // 2
    if feasible(mid):
        left = mid
    else:
        right = mid - 1
return left

Correct Implementation:

# CORRECT: Using template with first_true_index on inverted condition
left, right = 0, min(num_tasks, num_workers)
first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if not feasible(mid):  # Inverted: find first infeasible
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
# Answer is first_true_index - 1 (last feasible)
return first_true_index - 1 if first_true_index > 0 else (min(n, m) if first_true_index == -1 else 0)

2. Incorrect Worker Selection Strategy

Pitfall: A common mistake is trying to use the weakest workers first or randomly selecting workers, thinking we should "save" stronger workers for harder tasks.

Why it's wrong: This approach fails because:

  • Weak workers might not be able to complete any tasks even with pills
  • We waste pills on workers who can't contribute effectively
  • We miss opportunities where strong workers could complete tasks without pills

Solution: Always use the strongest k workers when trying to complete k tasks:

# CORRECT: Use strongest k workers
for worker_index in range(num_workers - k, num_workers):
    current_worker_strength = workers[worker_index]
    # ... rest of logic

3. Greedy Pill Usage on Wrong Tasks

Pitfall: When a worker needs a pill, assigning them to the easiest available task (from the front of the deque).

Why it's wrong: This wastes the pill's potential. If we use a pill, we should maximize its value by completing the hardest possible task.

Solution: When using a pill, assign the worker to the hardest available task:

# CORRECT: Using pill on hardest task
if available_tasks[0] <= current_worker_strength:
    available_tasks.popleft()  # No pill needed, take easiest
elif pills_remaining > 0:
    pills_remaining -= 1
    available_tasks.pop()  # With pill, take hardest task

4. Incorrect Task Availability Window

Pitfall: Adding tasks to the available queue based only on the worker's base strength, or adding all tasks at once.

Solution: Consider the worker's strength with a potential pill:

# CORRECT: Consider strength with pill
while task_index < k and tasks[task_index] <= current_worker_strength + strength:
    available_tasks.append(tasks[task_index])
    task_index += 1

These pitfalls often lead to incorrect results or runtime errors. The key insight is that the greedy strategy must be carefully implemented: use the strongest workers, and when pills are needed, maximize their value by completing the hardest possible tasks.

Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Greedy Introduction

Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning

Queue Intro

Queue Intro New to queues This article provides a quick review For a comprehensive beginner friendly lesson on queues check out our Foundation Course Queue module courses foundation queue_fifo_model Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More