2259. Remove Digit From Number to Maximize Result

EasyGreedyStringEnumeration
Leetcode Link

Problem Description

In this problem, you have a string number which represents a positive integer, and a character digit which is guaranteed to appear at least once in number. Your task is to remove exactly one occurrence of digit from number, such that the new string still represents a positive integer and is as large as possible. The challenge lies in determining which occurrence of the digit to remove in order to maximize the resulting integer.

Intuition

To arrive at the solution for this problem, it is beneficial to understand that the value of a digit in a number is dependent on its position. Specifically, the closer a digit is to the start of the number, the greater its impact on the number's overall value. Therefore, to maximize the result, we should prefer to remove a digit that is earlier in the string if it would lead to a larger subsequent digit being moved one position to the left.

The presented code iterates through the number string and checks each occurrence of digit. The core idea is to find the first instance of digit which is followed by a larger digit. When this pattern is found, removing the digit would result in increasing the overall number by having the larger digit take a more significant place. If this situation is not encountered, the code defaults to removing the last occurrence of digit, because removing a digit closer to the end of the number has the least impact on the number's value.

Thus, by scanning left to right and leveraging the significance of digit positions, we can decide on the optimal digit to remove to maximize the integer's value.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The implementation of the solution uses a simple for-loop to iterate over each character in the string number. The primary data structure used here is the string itself, as we are only interested in reading its characters without the need for additional data structures.

Here is the step-by-step approach of the algorithm:

  1. Initialize a variable last with -1, which will keep track of the index of the digit to be removed.
  2. Determine the length of number and store it in the variable n.
  3. Loop through each character d in number using its index i. For each character: a. Check if d equals digit. If it does: b. Update last with the current index i. c. If this is not the last character in the string, and if the current digit is less than the character following it, break the loop.
  4. After exiting the loop, return the resulting string by concatenating the substring of number before the index last and the substring of number after index last. We skip last itself to "remove" the digit.

This approach leverages pattern recognition – specifically, that removing a lower digit before a higher digit will maximize the resulting number. Furthermore, it falls back on the greedy algorithm principle where local choices are made (removing the first digit before a larger digit) in hopes of finding a global optimum – the largest possible number after removal.

This methodology guarantees that the most significant (and the first removable) digit that leads to an increase in value is removed. The simplicity and efficiency of iterating once through the string make this solution optimal for the given task.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's use a small example to illustrate the solution approach.

Suppose the number given is "2736" and the digit we need to remove is '3'. Following the solution approach described:

  1. We initialize last with -1. This variable will eventually hold the index of the '3' we choose to remove.

  2. We determine that the length of number (n) is 4.

  3. We loop through each character d in "2736" using its index i:

    • At index i = 0, d is '2'. It is not equal to '3', so we continue.
    • At index i = 1, d is '7'. Again, it is not '3', so we move on.
    • At index i = 2, d is '3'. This matches our digit. We update last to 2. Now, we look ahead to the next character.
    • The character following '3' is '6', which is greater than '3'. This means removing '3' from this position will maximize our result, as '6' will take a more significant place. We break the loop.

  4. Exiting the loop, we now know the index at last (2 in this case) is where we want to remove our digit. We return the resulting string by concatenating the substring before index last ("27") with the substring after index last ("6"), effectively skipping the '3'. The result is "276".

By this approach, we have successfully removed one instance of '3' from the number "2736" to get the largest possible new number, which is "276". The algorithm smartly picked the '3' that preceded a larger number, thus ensuring the maximization of the resulting integer.

Solution Implementation

1class Solution:
2    def removeDigit(self, number: str, digit_to_remove: str) -> str:
3        # Initialize variable to keep track of the position where
4        # the last occurrence of the digit to remove is found
5        last_occurrence_index = -1
6        # Calculate the length of the input number string
7        number_length = len(number)
8        # Loop through each character in the number string by index and value
9        for index, digit in enumerate(number):
10            # If the current digit is the one we want to remove, update the last occurrence index
11            if digit == digit_to_remove:
12                last_occurrence_index = index
13                # Check if there's a next digit and if it's greater than the current digit,
14                # in which case, we break out of the loop to remove this particular occurrence
15                if index + 1 < number_length and digit < number[index + 1]:
16                    break
17        # Return the number string with the digit removed at the last occurrence index
18        # This concatenation skips the digit to remove
19        return number[:last_occurrence_index] + number[last_occurrence_index + 1:]
20
1class Solution {
2    public String removeDigit(String number, char digit) {
3        int lastIndexOccurrence = -1; // Initialize the last index of the digit to be removed
4        int stringLength = number.length(); // Get the length of the number string
5
6        // Iterate through each character of the string
7        for (int i = 0; i < stringLength; ++i) {
8            char currentDigit = number.charAt(i); // Get the character at the current index
9          
10            // Check if the current character matches the digit we want to remove
11            if (currentDigit == digit) {
12                lastIndexOccurrence = i; // Update the last index occurrence of the digit
13              
14                // If the digit to remove is smaller than the next digit,
15                // and there is a next digit, break the loop
16                if (i + 1 < stringLength && currentDigit < number.charAt(i + 1)) {
17                    break;
18                }
19            }
20        }
21      
22        // Remove the digit at the last index occurrence and return the new string
23        return number.substring(0, lastIndexOccurrence) + number.substring(lastIndexOccurrence + 1);
24    }
25}
26
1class Solution {
2public:
3    /**
4     * Remove a single occurrence of the digit in the string such that the result is the largest possible number.
5     * 
6     * @param number The string representation of the number.
7     * @param digit The digit to remove.
8     * @return The result string after the digit is removed.
9     */
10    string removeDigit(string number, char digit) {
11        int numSize = number.size(); // Get the size of the number string.
12        int lastOccurrence = -1; // Track the last occurrence index of the digit.
13
14        // Iterate through the string.
15        for (int i = 0; i < numSize; ++i) {
16            char currentDigit = number[i]; // Store the current digit.
17
18            // Check if the current digit matches the digit we want to remove.
19            if (currentDigit == digit) {
20                lastOccurrence = i; // Update the last occurrence index.
21              
22                // Check if removing the current digit makes the number larger
23                // by comparing it with the next digit.
24                if (i + 1 < numSize && number[i] < number[i + 1]) {
25                    // If the next digit is larger, break the loop as we've found the optimal digit to remove.
26                    break;
27                }
28            }
29        }
30      
31        // Remove the digit from the number using the last occurrence found.
32        // Form a new string without the digit at the last occurrence index.
33        return number.substr(0, lastOccurrence) + number.substr(lastOccurrence + 1);
34    }
35};
36
1/**
2 * Removes the first occurrence of a given digit that is followed by a larger digit,
3 * or removes the last occurrence of the digit if no such condition is met.
4 * 
5 * @param {string} number - The original number represented as a string.
6 * @param {string} digit - The digit to be removed from the number.
7 * @returns {string} - The modified number as a string after removing the specified digit.
8 */
9function removeDigit(number: string, digit: string): string {
10    // Determine the length of the number string.
11    const numberLength: number = number.length;
12  
13    // Initialize an index to store the position of the digit to be removed.
14    let lastOccurrenceIndex: number = -1;
15  
16    // Iterate through each character in the number string.
17    for (let i = 0; i < numberLength; ++i) {
18        // Check if the current character is the digit we want to remove.
19        if (number[i] === digit) {
20            // Update the last occurrence index of the digit to the current index.
21            lastOccurrenceIndex = i;
22          
23            // Check if the current digit is followed by a larger digit.
24            if (i + 1 < numberLength && number[i] < number[i + 1]) {
25                // If so, break the loop as we've found the optimal digit to remove.
26                break;
27            }
28        }
29    }
30  
31    // Combine the parts of the string before and after the digit to be removed,
32    // effectively removing the digit from the number.
33    return number.substring(0, lastOccurrenceIndex) + number.substring(lastOccurrenceIndex + 1);
34}
35
Not Sure What to Study? Take the 2-min Quiz：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the string number. This is because the code involves a single for-loop over the string number, where each iteration performs a constant amount of work.

The space complexity of the given code is O(n). This is due to the string slicing operation number[:last] + number[last + 1 :], which creates a new string that can be of length up to n. Even though Python strings are immutable and slicing creates a new string, it is essential to note that slicing may leverage copy-on-write under the hood, where the actual complexity can depend on the Python implementation. However, for complexity analysis, it is safe to state that in the worst case the space complexity is linear with respect to the length of the input string.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫