Merge Two 2D Arrays by Summing Values
Problem Statement
You are given two 2D integer arrays nums1 and nums2.
nums1[i] = [idᵢ, valᵢ] indicate that the number with the idᵢ has a value equal to valᵢ.
nums2[i] = [idᵢ, valᵢ] indicate that the number with the idᵢ has a value equal to valᵢ.
Each array contains unique ids and is sorted in ascending order by id.
Merge the two arrays into one array that is sorted in ascending order by id, respecting the following conditions:
Only ids that appear in at least one of the two arrays should be included in the resulting array.
Each id should be included only once and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays then its value in that array is considered to be 0.
Return the resulting array. The returned array must be sorted in ascending order by id.
Examples
Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
Output: [[1,6],[2,3],[3,2],[4,6]]
Explanation: The resulting array contains the following:
- id = 1, the value of this id is 2 + 4 = 6.
- id = 2, the value of this id is 3.
- id = 3, the value of this id is 2.
- id = 4, the value of this id is 5 + 1 = 6.
Input: nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
Output: [[1,3],[2,4],[3,6],[4,3],[5,5]]
Explanation: There are no common ids, so we just include each id with its value in the resulting list.
Constraints
- 1 <= nums1.length, nums2.length <= 200
- nums1[i].length == nums2[j].length == 2
- 1 <= idᵢ, valᵢ <= 1000
- Both arrays contain unique ids.
- Both arrays are in strictly ascending order by id.
The problem appears to involve simulation, where we follow the specified instructions. We simply need to sum the values associated with the same ID. If an ID is missing in one of the sets, we treat its value as 0 for the addition.
Brute Force approach
When reading the problem description, the first thought is to efficiently combine the values for each unique ID from both arrays, given that the IDs are unique and already sorted.
A straightforward solution is to use a std::map to store and sum the values for each ID.
Why map?
We use a std::map for this problem because it simplifies the process of merging the two arrays while meeting all the requirements. The map allows efficient insertion and lookup, making it easy to add or update the value for each unique ID. Since the map automatically keeps the keys (IDs) sorted, we don’t need an additional step to sort the result. As we process both arrays, the map ensures each ID appears only once, consolidating the values for IDs present in both arrays. This combination of efficient data handling and automatic sorting makes the map an ideal choice for solving the problem cleanly and effectively.
We start by iterating through all the elements in nums1, adding each ID and its value to the map. Next, we repeat the process for nums2, adding its values to the map as well. If an ID is already present, we simply add the new value to the existing one. After processing both arrays, the map will contain all unique IDs along with their combined values. Finally, we convert the map into a sorted 2D vector of [ID, value] pairs and return it.
This method is effective because the map automatically keeps the IDs sorted and simplifies the process of summing the values.
Let's Understand with an example
Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
Step-by-Step Execution:
- Initialize the Map:
- An empty map<int, int> is created to store the IDs as keys and their corresponding summed values as values.
Processing nums1:
- Traverse nums1 and update the map:
- First Element: [1, 2]
Add ID 1 with value 2:
mergedMap = {1: 2} - Second Element: [2, 3]
Add ID 2 with value 3:
mergedMap = {1: 2, 2: 3} - Third Element: [4, 5]
Add ID 4 with value 5:
mergedMap = {1: 2, 2: 3, 4: 5}
- First Element: [1, 2]
Processing nums2:
- Traverse nums2 and update the map:
- First Element: [1, 4]
ID 1 already exists in the map with the value 2. Add 4 to it:
mergedMap = {1: 6, 2: 3, 4: 5} - Second Element: [3, 2]
ID 3 is not in the map. Add it with value 2:
mergedMap = {1: 6, 2: 3, 3: 2, 4: 5} - Third Element: [4, 1]
ID 4 already exists in the map with value 5. Add 1 to it:
mergedMap = {1: 6, 2: 3, 3: 2, 4: 6}
- First Element: [1, 4]
Prepare the Result:
- Traverse the mergedMap to construct the final result:
- Extract each (ID, value) pair in ascending order of IDs.
- Add [1, 6], [2, 3], [3, 2], and [4, 6] to the result vector.
Final Output: result = [[1,6], [2,3], [3,2], [4,6]]
Step to write code
Initialize the Map:
- Inside the function, declare a map<int, int> to store the IDs as keys and their summed values as values.
Traverse the First Array:
- Loop through each pair in nums1.
- Extract the ID and value from the current pair.
- Add the value to the map for the corresponding ID. If the ID is already present, the map will automatically sum the values.
Traverse the Second Array:
- Repeat the same process for nums2.
- Extract the ID and value from the current pair and update the map by summing the values.
Prepare the Result Vector:
- Declare a vector<vector<int>> to store the merged output.
Traverse the Map:
- Iterate through the map (sorted by default in ascending order of keys).
- For each (key, value) pair, create a vector {key, value} and add it to the result vector.
Return the Result:
- Return the result vector containing the merged data.
Code for All Languages
C++
class Solution {
public:
vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
// Declare a map to store the merged values.
// The key will be the ID, and the value will be the sum of values corresponding to that ID.
map<int, int> mergedMap;
// Traverse the first array and populate the map.
for (const auto& pair : nums1) {
// Extract the ID.
int id = pair[0];
// Extract the value.
int value = pair[1];
// Add the value to the map for the corresponding ID.
mergedMap[id] += value;
}
// Traverse the second array and update the map.
for (const auto& pair : nums2) {
// Extract the ID.
int id = pair[0];
// Extract the value.
int value = pair[1];
// Add the value to the map for the corresponding ID.
mergedMap[id] += value;
}
// Prepare the result vector.
vector<vector<int>> result;
// Traverse the map to create the final merged array.
for (const auto& entry : mergedMap) {
// Get the ID.
int id = entry.first;
// Get the summed value for this ID.
int value = entry.second;
// Add the pair to the result vector.
result.push_back({id, value});
}
// Return the result vector.
return result;
}
};
Java
class Solution {
public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
// Declare a TreeMap to store the merged values.
// The key will be the ID, and the value will be the sum of values corresponding to that ID.
TreeMap<Integer, Integer> mergedMap = new TreeMap<>();
// Traverse the first array and populate the map.
for (int[] pair : nums1) {
// Extract the ID.
int id = pair[0];
// Extract the value.
int value = pair[1];
// Add the value to the map for the corresponding ID.
mergedMap.put(id, mergedMap.getOrDefault(id, 0) + value);
}
// Traverse the second array and update the map.
for (int[] pair : nums2) {
// Extract the ID.
int id = pair[0];
// Extract the value.
int value = pair[1];
// Add the value to the map for the corresponding ID.
mergedMap.put(id, mergedMap.getOrDefault(id, 0) + value);
}
// Prepare the result array.
int[][] result = new int[mergedMap.size()][2];
int index = 0;
// Traverse the map to create the final merged array.
for (Map.Entry<Integer, Integer> entry : mergedMap.entrySet()) {
// Get the ID.
int id = entry.getKey();
// Get the summed value for this ID.
int value = entry.getValue();
// Add the pair to the result array.
result[index++] = new int[] {id, value};
}
// Return the result array.
return result;
}
}
Python
class Solution(object):
def mergeArrays(self, nums1, nums2):
"""
:type nums1: List[List[int]]
:type nums2: List[List[int]]
:rtype: List[List[int]]
"""
# Declare a dictionary to store the merged values.
# The key will be the ID, and the value will be the sum of values corresponding to that ID.
merged_dict = {}
# Traverse the first array and populate the dictionary.
for pair in nums1:
# Extract the ID.
id = pair[0]
# Extract the value.
value = pair[1]
# Add the value to the dictionary for the corresponding ID.
merged_dict[id] = merged_dict.get(id, 0) + value
# Traverse the second array and update the dictionary.
for pair in nums2:
# Extract the ID.
id = pair[0]
# Extract the value.
value = pair[1]
# Add the value to the dictionary for the corresponding ID.
merged_dict[id] = merged_dict.get(id, 0) + value
# Prepare the result list.
result = []
# Traverse the dictionary to create the final merged array.
for id in sorted(merged_dict.keys()):
# Add the ID and its summed value as a pair to the result list.
result.append([id, merged_dict[id]])
# Return the result list.
return result
Javascript
/**
* @param {number[][]} nums1
* @param {number[][]} nums2
* @return {number[][]}
*/
var mergeArrays = function(nums1, nums2) {
// Declare a Map to store the merged values.
// The key will be the ID, and the value will be the sum of values corresponding to that ID.
let mergedMap = new Map();
// Traverse the first array and populate the Map.
for (let [id, value] of nums1) {
// Add the value to the Map for the corresponding ID.
mergedMap.set(id, (mergedMap.get(id) || 0) + value);
}
// Traverse the second array and update the Map.
for (let [id, value] of nums2) {
// Add the value to the Map for the corresponding ID.
mergedMap.set(id, (mergedMap.get(id) || 0) + value);
}
// Prepare the result array.
let result = [];
// Traverse the Map to create the final merged array.
// Sort the keys in ascending order for the final result.
for (let [id, value] of Array.from(mergedMap.entries()).sort((a, b) => a[0] - b[0])) {
result.push([id, value]);
}
// Return the result array.
return result;
};
Time Complexity: O((n+m)log(n+m))
1. Inserting Elements from nums1 into mergedMap
- Operation: For each pair in nums1, we insert the ID and its value into the std::map.
- The std::map is implemented as a balanced binary search tree (e.g., Red-Black Tree). Each insertion or update in the map takes O(logk), where k is the current number of elements in the map.
- Work Done: If nums1 has n elements, we perform n insertions. Hence, this step takes O(nlogk), where k is the size of the map.
2. Updating the Map with Elements from nums2
- Operation: Similarly, for each pair in nums2, we update or insert the ID and its value into the std::map.
- Again, each insertion or update in the map takes O(logk), where k is the current size of the map.
- Work Done: If nums2 has mmm elements, this step takes O(mlogk).
3. Iterating Over the Map to Construct the Result
- Operation: Once the map is populated, we traverse it to construct the result vector.
- Traversing all k keys in the map takes O(k), and adding each key-value pair to the result vector takes constant time per pair.
- Work Done: This step takes O(k).
Overall Time Complexity
- Processing nums1: O(nlogk)
- Processing nums2: O(mlogk)
- Constructing the result: O(k)
In the worst case, k=n+m because all IDs from both arrays could be unique. Substituting k=n+m, the time complexity
becomes: O(nlog(n+m))+O(mlog(n+m))+O(n+m)
This simplifies to: O((n+m)log(n+m))
Space Complexity: O(n+m)
1. Map (std::map)
- The std::map is used to store the merged results of the IDs and their corresponding summed values.
- In the worst case, the number of unique IDs in the map is equal to the total number of IDs in nums1 and nums2. This happens when there are no overlapping IDs between the two arrays.
- Each entry in the map requires:
- Memory for the key (the ID, an integer): O(1).
- Memory for the value (the sum of values for that ID, an integer): O(1).
- Overhead for the tree structure of the map, which is logarithmic with respect to the number of entries. For k entries, the overhead is O(k).
Thus, the map requires O(k) space for storing the keys and values, where k is the number of unique IDs, and k≤n+m.
2. Result Vector
- The result vector stores the final merged array as a list of pairs [id, value].
- In the worst case, the number of entries in the result vector is equal to the number of unique IDs, k, because each unique ID corresponds to one pair.
- Each pair [id, value] requires O(2) space (two integers).
- Thus, the result vector uses O(k) space.
3. Input Data
- The input arrays nums1 and nums2 are provided as arguments, so they don’t contribute to the algorithm’s space usage.
- However, their combined size is O(n+m), where n and m are the sizes of nums1 and nums2, respectively.
4. Auxiliary Space
- Apart from the map and result vector, the algorithm uses a constant amount of space for variables (e.g., loop counters, temporary variables like id and value).
- This contributes O(1) to the space complexity.
Total Space Complexity
- The dominant contributors to the space complexity are the map and the result vector.
- Both the map and the result vector require O(k) space, where k≤n+m.
- The total space complexity is therefore: O(n+m)
Will this work under given constraints?
The brute force map-based approach will work efficiently within the given constraints. Since both input arrays are strictly sorted by unique IDs and their lengths are limited to a maximum of 200, the operations involved are computationally feasible.
The approach involves iterating through both arrays, which has a linear time complexity of O(n+m), where n and m are the lengths of the two arrays. Each insertion or update in the map has an average time complexity of O(1) (for hash maps) or O(log(n+m))(for ordered maps, such as C++'s std::map), where k is the number of unique IDs.
After merging the arrays, the IDs are sorted, which requires O((n+m)log(n+m)). With n+m≤400 and k≤n+m, the total time complexity, O(n+m+(n+m)log(n+m)), remains efficient.
The space complexity is O(n+m), as the map stores all unique IDs and their corresponding values. Given these considerations, the map-based approach is well-suited to the constraints, but alternative methods like two-pointer merging may be considered for even larger input sizes.
Two Pointer Approach
Since the brute force approach uses an extra data structure map, can we optimize it?
Instead of using an extra data structure like a map, we can directly merge the two arrays using a two-pointer approach, which is both simple and efficient. Since the arrays are already sorted and each id in the array is unique, we can use two indices(i, j) to move through them. At each step, compare the IDs at the current positions.
If one ID is smaller, add that element to the result and move the pointer for that array. If the IDs are the same, combine their values, add the result to the output, and move both pointers forward. Once one of the arrays is fully processed, add the remaining elements from the other array to the result.
Let's Understand with an example
Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
- nums1 and nums2 are both sorted by their IDs (the first element in each sub-array).
- The goal is to merge these two arrays while summing up the values (second elements) for matching IDs and maintaining the sorted order.
Step-by-Step Execution:
- Initialize Result and Pointers:
- result is initialized as an empty vector.
- Two pointers, i and j, are set to 0 to traverse nums1 and nums2.
- First Iteration (i=0, j=0):
- Compare nums1[0][0] (ID 1) with nums2[0][0] (ID 1).
- The IDs are the same 1, so their values (2 and 4) are summed: 2 + 4 = 6.
- Add [1,6] to the result and increment both pointers: i=1, j=1.
- Result so far: [[1,6]]
- Second Iteration (i=1, j=1):
- Compare nums1[1][0] (ID 2) with nums2[1][0] (ID 3).
- ID 2 is smaller, so add [2,3] (from nums1) to the result and increment i: i=2, j=1.
- Result so far: [[1,6], [2,3]]
- Third Iteration (i=2, j=1):
- Compare nums1[2][0] (ID 4) with nums2[1][0] (ID 3).
- ID 3 is smaller, so add [3,2] (from nums2) to the result and increment j: i=2, j=2.
- Result so far: [[1,6], [2,3], [3,2]]
- Fourth Iteration (i=2, j=2):
- Compare nums1[2][0] (ID 4) with nums2[2][0] (ID 4).
- The IDs are the same (4), so their values (5 and 1) are summed: 5 + 1 = 6.
- Add [4,6] to the result and increment both pointers: i=3, j=3.
- Result so far: [[1,6], [2,3], [3,2], [4,6]]
- Check for Remaining Elements:
- Both nums1 and nums2 are fully processed (i=3, j=3), so no further elements need to be added.
Final Output: result = [[1,6], [2,3], [3,2], [4,6]]
Steps to write code
- Initialize the Result Vector:
Create a vector called result to store the merged output. This will hold the final combined list of elements from both input arrays. - Initialize Two Pointers:
Use two integer variables, i and j, initialized to 0. These pointers will traverse nums1 and nums2, respectively. - Traverse Both Arrays Simultaneously:
Use a while loop to iterate as long as neither of the pointers has reached the end of its respective array. - Compare the IDs (the first elements of the sub-arrays) at the current positions of nums1[i] and nums2[j].
- If the ID in nums1[i] is smaller, add the current element of nums1 to the result and increment i.
- If the ID in nums2[j] is smaller, add the current element of nums2 to the result and increment j.
- If the IDs are equal, sum their values, add the combined pair to the result, and increment both i and j.
- Add Remaining Elements from nums1:
After the main loop, check if there are any elements left in nums1 using another while loop. If so, add them to the result. - Add Remaining Elements from nums2:
Similarly, check if there are any remaining elements in nums2 and append them to the result. - Return the Result:
Once all elements from both arrays are processed and merged, return theresult
vector.
Code for All Languages
C++
class Solution {
public:
vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
// Initialize result vector to store the merged output.
vector<vector<int>> result;
// Use two pointers to traverse both arrays.
int i = 0, j = 0;
// Loop until we traverse both arrays completely.
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i][0] < nums2[j][0]) {
// If ID in nums1 is smaller, add it to the result.
result.push_back(nums1[i]);
i++;
} else if (nums1[i][0] > nums2[j][0]) {
// If ID in nums2 is smaller, add it to the result.
result.push_back(nums2[j]);
j++;
} else {
// If IDs are equal, sum their values and add to the result.
result.push_back({nums1[i][0], nums1[i][1] + nums2[j][1]});
i++;
j++;
}
}
// Add remaining elements from nums1, if any.
while (i < nums1.size()) {
result.push_back(nums1[i]);
i++;
}
// Add remaining elements from nums2, if any.
while (j < nums2.size()) {
result.push_back(nums2[j]);
j++;
}
// Return the merged result.
return result;
}
};
Java
import java.util.*;
class Solution {
public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
// Initialize a list to store the merged output.
List<int[]> result = new ArrayList<>();
// Use two pointers to traverse both arrays.
int i = 0, j = 0;
// Loop until we traverse both arrays completely.
while (i < nums1.length && j < nums2.length) {
if (nums1[i][0] < nums2[j][0]) {
// If ID in nums1 is smaller, add it to the result.
result.add(nums1[i]);
i++;
} else if (nums1[i][0] > nums2[j][0]) {
// If ID in nums2 is smaller, add it to the result.
result.add(nums2[j]);
j++;
} else {
// If IDs are equal, sum their values and add to the result.
result.add(new int[]{nums1[i][0], nums1[i][1] + nums2[j][1]});
i++;
j++;
}
}
// Add remaining elements from nums1, if any.
while (i < nums1.length) {
result.add(nums1[i]);
i++;
}
// Add remaining elements from nums2, if any.
while (j < nums2.length) {
result.add(nums2[j]);
j++;
}
// Convert the list to an array and return.
return result.toArray(new int[result.size()][]);
}
}
Python
class Solution:
def mergeArrays(self, nums1, nums2):
"""
:type nums1: List[List[int]]
:type nums2: List[List[int]]
:rtype: List[List[int]]
"""
# Initialize result list to store the merged output.
result = []
# Use two pointers to traverse both arrays.
i, j = 0, 0
# Loop until we traverse both arrays completely.
while i < len(nums1) and j < len(nums2):
if nums1[i][0] < nums2[j][0]:
# If ID in nums1 is smaller, add it to the result.
result.append(nums1[i])
i += 1
elif nums1[i][0] > nums2[j][0]:
# If ID in nums2 is smaller, add it to the result.
result.append(nums2[j])
j += 1
else:
# If IDs are equal, sum their values and add to the result.
result.append([nums1[i][0], nums1[i][1] + nums2[j][1]])
i += 1
j += 1
# Add remaining elements from nums1, if any.
while i < len(nums1):
result.append(nums1[i])
i += 1
# Add remaining elements from nums2, if any.
while j < len(nums2):
result.append(nums2[j])
j += 1
# Return the merged result.
return result
Javascript
/**
* @param {number[][]} nums1
* @param {number[][]} nums2
* @return {number[][]}
*/
var mergeArrays = function(nums1, nums2) {
// Initialize result array to store the merged output.
const result = [];
// Use two pointers to traverse both arrays.
let i = 0, j = 0;
// Loop until we traverse both arrays completely.
while (i < nums1.length && j < nums2.length) {
if (nums1[i][0] < nums2[j][0]) {
// If ID in nums1 is smaller, add it to the result.
result.push(nums1[i]);
i++;
} else if (nums1[i][0] > nums2[j][0]) {
// If ID in nums2 is smaller, add it to the result.
result.push(nums2[j]);
j++;
} else {
// If IDs are equal, sum their values and add to the result.
result.push([nums1[i][0], nums1[i][1] + nums2[j][1]]);
i++;
j++;
}
}
// Add remaining elements from nums1, if any.
while (i < nums1.length) {
result.push(nums1[i]);
i++;
}
// Add remaining elements from nums2, if any.
while (j < nums2.length) {
result.push(nums2[j]);
j++;
}
// Return the merged result.
return result;
};
Time Complexity: O(n+m)
1. Main While Loop
- The main while loop runs as long as there are elements left in both nums1 and nums2.
- Operation: At each step of the loop, we compare the current IDs of nums1[i] and nums2[j]:
- If the ID in nums1 is smaller, we add it to the result and move the pointer i forward.
- If the ID in nums2 is smaller, we add it to the result and move the pointer j forward.
- If the IDs are equal, we sum their values, add the result to the output, and move both i and j forward.
- Each comparison and insertion into the result vector takes constant time, O(1).
- Number of Iterations: Since we process one element from either nums1 or nums2 in each iteration, the total number of iterations is proportional to n+m, where n=nums1.size() and m=nums2.size()).
- Time for this step: O(n+m).
2. Remaining Elements (Two While Loops)
- After exiting the main loop, at most one of the arrays will still have unprocessed elements. The remaining elements are added to the result vector using two separate while loops.
- Operation: Each remaining element is directly appended to the result vector in constant time, O(1).
- Number of Iterations: The combined number of remaining elements is at most n+m.
- Time for this step: O(n+m).
3. Overall Time Complexity
- The main while loop processes all elements from both arrays in O(n+m).
- The two while loops for the remaining elements also take O(n+m) in the worst case.
- Combining these, the overall time complexity is: O(n+m)
This is the optimal complexity for this problem since we must examine all elements of both arrays at least once.
Space Complexity: O(1)
- Result Vector (result)
- The solution requires a vector<vector<int>> result to store the merged output.
- The size of the result depends on the total number of elements in the two input arrays, nums1 and nums2.
- In the worst case, all IDs from nums1 and nums2 are unique, meaning the total size of result will be n+m, where:
- n=nums1.size()
- m=nums2.size()
- Hence, the result vector takes O(n+m) space.
2. Pointers and Variables
- The algorithm uses two integer variables, i and j, as pointers to traverse nums1 and nums2. Additionally, there are temporary variables to hold IDs and values during comparisons.
- These variables require constant space, O(1).
3. Input Arrays
- The input arrays nums1 and nums2 are provided as arguments and do not contribute to additional space usage for this algorithm since we are not making copies of them.
Total Space Complexity
- The dominant factor is the space used by the result vector, which is proportional to the total number of elements in the input arrays, n+mn + mn+m.
- Since the extra space used for pointers and variables is constant, it does not affect the overall space complexity.
- Therefore, the total space complexity is: O(n+m)
Key Takeaways
Having learned the optimal algorithm for "Merge Two 2D Arrays by Summing Values", you can now apply this algorithm to different problems. Additionally, you can attempt to solve the following problems by utilizing this approach.
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
You are given two strings word1 and word2. You want to construct a string merge in the following way: while either word1 or word2 are non-empty, choose one of the following options:
If word1 is non-empty, append the first character in word1 to merge and delete it from word1.
For example, if word1 = "abc" and merge = "dv", then after choosing this operation, word1 = "bc" and merge = "dva".
If word2 is non-empty, append the first character in word2 to merge and delete it from word2.
For example, if word2 = "abc" and merge = "", then after choosing this operation, word2 = "bc" and merge = "a".
Return the lexicographically largest merge you can construct.
A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b.
For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.