# Largest Number

## 1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?
• How do we construct the largest number?
• Ensure that the most significant digits are occupied by the largest digits.
• Why is it that when input is 2048, and "8420" is returned, that is the wrong answer?
• You cannot arrange the individual numbers. you can only change the order of given numbers but not their digits.
• What are the constraints?
• Constraints: 1 <= nums.length <= 100 and 0 <= nums[i] <= 109
``````HAPPY CASE
Input: nums = [10,2]
Output: "210"

EDGE CASE
Input: nums = [3,30,34,5,9]
Output: "9534330"``````

## 2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

• The Greedy Algorithm always choose the best at the current iteration. Given two numbers a and b, we pick the larger number if the string concatenation of a+b is bigger than b+a. If we compare any 2 non-overlapping substrings of some number x, we can determine what order the substrings must appear in x.

## 3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the array, the most "signficant" number will be at the front.

``````1. Convert each integer to a string. Then, we sort the array of strings.
2. Once the array is sorted, the most "signficant" number will be at the front. There is a minor edge case that comes up when the array consists of only zeroes, so if the most significant number is 00, we can simply return 00. Otherwise, we build a string out of the sorted array and return it.``````

⚠️ Common Mistakes

• What are some common pitfalls students might have when implementing this solution?

• If you are struggling to implement, try using a comparator. For example, a, b are the two strings obtained from the array passed into the sort() in java.

(a+b).compareTo(b+a) returns the smallest possible order. (b+a).compareTo(a+b) returns the largest possible order. If the zero flag case is not handled, only 226 out of 230 cases will pass. Suppose the array had only zeroes: [0,0]. Then, the string array would have ["0", "0"] and result would return "00" instead of "0". So, if all the elements in the array is 0, then simply return 0.

## 4: I-mplement

Implement the code to solve the algorithm.

``````class LargerNumKey(str):
def __lt__(x, y):
return x+y > y+x

class Solution:
def largestNumber(self, nums):
largest_num = ''.join(sorted(map(str, nums), key=LargerNumKey))
return '0' if largest_num[0] == '0' else largest_num``````
``````class Solution {
private class LargerNumberComparator implements Comparator<String> {
@Override
public int compare(String a, String b) {
String order1 = a + b;
String order2 = b + a;
return order2.compareTo(order1);
}
}

public String largestNumber(int[] nums) {
// get input integers as strings.
String[] asStrs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
asStrs[i] = String.valueOf(nums[i]);
}

// sort strings according to custom comparator.
Arrays.sort(asStrs, new LargerNumberComparator());

// ff, after being sorted, the largest number is `0`, the entire number
// is zero.
if (asStrs[0].equals("0")) {
return "0";
}

// build largest number from sorted array.
String largestNumberStr = new String();
for (String numAsStr : asStrs) {
largestNumberStr += numAsStr;
}

return largestNumberStr;
}
}``````

## 5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Trace through your code with an input to check for the expected output
• Catch possible edge cases and off-by-one errors

## 6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

• Time Complexity: O(nlgn), the sort functionality in Python and Java is O(nlgn).
• Space Complexity: O(n), we allocate O(n) additional space to store the copy of nums.