646. Maximum Length of Pair Chain
Explanation:
To solve this problem, we can sort the pairs based on their ending values. We then iterate through the sorted pairs, keeping track of the maximum chain length we can form up to that point. We update this maximum chain length by comparing it with the previous pairs' ending values. By the end of the iteration, we will have the longest chain length that can be formed.
- Sort the pairs based on the ending values.
- Initialize a variable
maxLengthto keep track of the maximum chain length. - Iterate through the sorted pairs:
- If the current pair's start value is greater than the previous pair's end value, increment
maxLengthand update the previous pair's end value.
- If the current pair's start value is greater than the previous pair's end value, increment
- Return
maxLength.
Time Complexity: O(n log n) - Sorting the pairs Space Complexity: O(1) - Constant space used
:
class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a, b) -> Integer.compare(a[1], b[1]));
int maxLength = 1;
int prevEnd = pairs[0][1];
for (int i = 1; i < pairs.length; i++) {
if (pairs[i][0] > prevEnd) {
maxLength++;
prevEnd = pairs[i][1];
}
}
return maxLength;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.