1 Remove Duplicates from Sorted Array
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new
length. Do not allocate extra space for another array, you must do this in place with constant memory.
For example, given input array A = [1,1,2], your function should return length = 2, and A is now [1,2].
1.1 Analysis
The problem is pretty straightforward. It returns the length of the array with unique elements, but the original
array need to be changed also. This problem is similar to Remove Duplicates from Sorted Array II.
1.2 Java Solution
public static int removeDuplicates(int[] A) {
if ([Link] < 2)
return [Link];
int j = 0;
int i = 1;
while (i < [Link]) {
if (A[i] != A[j]) {
j++;
A[j] = A[i];
}
i++;
}
return j + 1;
}
14 | 568
1 Remove Duplicates from Sorted Array
Note that we only care about the first unique part of the original array. So it is ok if input array is 1, 2, 2, 3, 3,
the array is changed to 1, 2, 3, 3, 3.
Program Creek 15 | 568
2 Remove Duplicates from Sorted Array II
Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?
For example, given sorted array A = [1,1,1,2,2,3], your function should return length = 5, and A is now [1,1,2,2,3].
So this problem also requires in-place array manipulation.
2.1 Java Solution 1
We can not change the given array’s size, so we only change the first k elements of the array which has duplicates
removed.
public int removeDuplicates(int[] nums) {
if(nums==null){
return 0;
}
if([Link]<3){
return [Link];
}
int i=0;
int j=1;
/*
i, j 1 1 1 2 2 3
step1 0 1 i j
step2 1 2 i j
step3 1 3 i j
step4 2 4 i j
*/
while(j<[Link]){
if(nums[j]==nums[i]){
if(i==0){
i++;
j++;
}else if(nums[i]==nums[i-1]){
j++;
}else{
i++;
nums[i]=nums[j];
j++;
}
}else{
i++;
nums[i]=nums[j];
j++;
}
}
return i+1;
}
16 | 568
2 Remove Duplicates from Sorted Array II
The problem with this solution is that there are 4 cases to handle. If we shift our two points to right by 1
element, the solution can be simplified as the Solution 2.
2.2 Java Solution 2
public int removeDuplicates(int[] nums) {
if(nums==null){
return 0;
}
if ([Link] <= 2){
return [Link];
}
/*
1,1,1,2,2,3
i j
*/
int i = 1; // point to previous
int j = 2; // point to current
while (j < [Link]) {
if (nums[j] == nums[i] && nums[j] == nums[i - 1]) {
j++;
} else {
i++;
nums[i] = nums[j];
j++;
}
}
return i + 1;
}
Program Creek 17 | 568
3 Remove Element
Given an array and a value, remove all instances of that value in place and return the new length. (Note: The
order of elements can be changed. It doesn’t matter what you leave beyond the new length.)
3.1 Java Solution
This problem can be solve by using two indices.
public int removeElement(int[] A, int elem) {
int i=0;
int j=0;
while(j < [Link]){
if(A[j] != elem){
A[i] = A[j];
i++;
}
j++;
}
return i;
}
18 | 568
4 Move Zeroes
Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the
non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
4.1 Java Solution 2
We can use the similar code that is used to solve Remove Duplicates from Sorted Array I, II, Remove Element.
public void moveZeroes(int[] nums) {
int i=0;
int j=0;
while(j<[Link]){
if(nums[j]==0){
j++;
}else{
nums[i]=nums[j];
i++;
j++;
}
}
while(i<[Link]){
nums[i]=0;
i++;
}
}
19 | 568
5 Candy
There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these
children subjected to the following requirements:
1. Each child must have at least one candy. 2. Children with a higher rating get more candies than their
neighbors.
What is the minimum candies you must give?
5.1 Analysis
This problem can be solved in O(n) time.
We can always assign a neighbor with 1 more if the neighbor has higher a rating value. However, to get the
minimum total number, we should always start adding 1s in the ascending order. We can solve this problem by
scanning the array from both sides. First, scan the array from left to right, and assign values for all the ascending
pairs. Then scan from right to left and assign values to descending pairs.
This problem is similar to Trapping Rain Water.
5.2 Java Solution
public int candy(int[] ratings) {
if (ratings == null || [Link] == 0) {
return 0;
}
int[] candies = new int[[Link]];
candies[0] = 1;
//from let to right
for (int i = 1; i < [Link]; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
} else {
// if not ascending, assign 1
candies[i] = 1;
}
}
int result = candies[[Link] - 1];
//from right to left
for (int i = [Link] - 2; i >= 0; i--) {
int cur = 1;
if (ratings[i] > ratings[i + 1]) {
cur = candies[i + 1] + 1;
}
result += [Link](cur, candies[i]);
candies[i] = cur;
}
20 | 568
5 Candy
return result;
}
Program Creek 21 | 568
6 Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how
much water it is able to trap after raining.
For example, given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
6.1 Analysis
This problem is similar to Candy. It can be solve by scanning from both sides and then get the total.
6.2 Java Solution
public int trap(int[] height) {
int result = 0;
if(height==null || [Link]<=2)
return result;
int left[] = new int[[Link]];
int right[]= new int[[Link]];
//scan from left to right
int max = height[0];
left[0] = height[0];
for(int i=1; i<[Link]; i++){
if(height[i]<max){
left[i]=max;
22 | 568
6 Trapping Rain Water
}else{
left[i]=height[i];
max = height[i];
}
}
//scan from right to left
max = height[[Link]-1];
right[[Link]-1]=height[[Link]-1];
for(int i=[Link]-2; i>=0; i--){
if(height[i]<max){
right[i]=max;
}else{
right[i]=height[i];
max = height[i];
}
}
//calculate totoal
for(int i=0; i<[Link]; i++){
result+= [Link](left[i],right[i])-height[i];
}
return result;
}
Program Creek 23 | 568
7 Product of Array Except Self
Given an array of n integers where n >1, nums, return an array output such that output[i] is equal to the product
of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
7.1 Java Solution 1
public int[] productExceptSelf(int[] nums) {
int[] result = new int[[Link]];
int[] t1 = new int[[Link]];
int[] t2 = new int[[Link]];
t1[0]=1;
t2[[Link]-1]=1;
//scan from left to right
for(int i=0; i<[Link]-1; i++){
t1[i+1] = nums[i] * t1[i];
}
//scan from right to left
for(int i=[Link]-1; i>0; i--){
t2[i-1] = t2[i] * nums[i];
}
//multiply
for(int i=0; i<[Link]; i++){
result[i] = t1[i] * t2[i];
}
return result;
}
7.2 Java Solution 2
We can directly put the product values into the final result array. This saves the extra space to store the 2
intermediate arrays in Solution 1.
public int[] productExceptSelf(int[] nums) {
int[] result = new int[[Link]];
result[[Link]-1]=1;
for(int i=[Link]-2; i>=0; i--){
result[i]=result[i+1]*nums[i+1];
}
24 | 568
7 Product of Array Except Self
int left=1;
for(int i=0; i<[Link]; i++){
result[i]=result[i]*left;
left = left*nums[i];
}
return result;
}
Program Creek 25 | 568
8 Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the
sum ≥ s. If there isn’t one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length of 2 under the
problem constraint.
8.1 Analysis
We can use 2 points to mark the left and right boundaries of the sliding window. When the sum is greater than
the target, shift the left pointer; when the sum is less than the target, shift the right pointer.
8.2 Java Solution - two pointers
A simple sliding window solution.
public int minSubArrayLen(int s, int[] nums) {
if(nums==null || [Link]==1)
return 0;
int result = [Link];
int start=0;
int sum=0;
int i=0;
boolean exists = false;
while(i<=[Link]){
if(sum>=s){
exists=true; //mark if there exists such a subarray
if(start==i-1){
return 1;
}
result = [Link](result, i-start);
sum=sum-nums[start];
start++;
}else{
if(i==[Link])
break;
sum = sum+nums[i];
i++;
}
}
if(exists)
return result;
else
return 0;
26 | 568
8 Minimum Size Subarray Sum
Similarly, we can also write it in a more readable way.
public int minSubArrayLen(int s, int[] nums) {
if(nums==null||[Link]==0)
return 0;
int i=0;
int j=0;
int sum=0;
int minLen = Integer.MAX_VALUE;
while(j<[Link]){
if(sum<s){
sum += nums[j];
j++;
}else{
minLen = [Link](minLen, j-i);
if(i==j-1)
return 1;
sum -=nums[i];
i++;
}
}
while(sum>=s){
minLen = [Link](minLen, j-i);
sum -=nums[i++];
}
return minLen==Integer.MAX_VALUE? 0: minLen;
}
Program Creek 27 | 568
9 Summary Ranges
Given a sorted integer array without duplicates, return the summary of its ranges for consecutive numbers.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].
9.1 Analysis
When iterating over the array, two values need to be tracked: 1) the first value of a new range and 2) the previous
value in the range.
9.2 Java Solution
public List<String> summaryRanges(int[] nums) {
List<String> result = new ArrayList<String>();
if(nums == null || [Link]==0)
return result;
if([Link]==1){
[Link](nums[0]+"");
}
int pre = nums[0]; // previous element
int first = pre; // first element of each range
for(int i=1; i<[Link]; i++){
if(nums[i]==pre+1){
if(i==[Link]-1){
[Link](first+"->"+nums[i]);
}
}else{
if(first == pre){
[Link](first+"");
}else{
[Link](first + "->"+pre);
}
if(i==[Link]-1){
[Link](nums[i]+"");
}
first = nums[i];
}
pre = nums[i];
}
return result;
}
28 | 568
10 Missing Ranges
Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return
its missing ranges.
Example:
Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99, Output: ["2", "4->49", "51->74", "76->99"]
10.1 Java Solution
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> result = new ArrayList<>();
int start = lower;
if(lower==Integer.MAX_VALUE){
return result;
}
for(int i=0; i<[Link]; i++){
//handle duplicates, e.g., [1,1,1] lower=1 upper=1
if(i<[Link]-1 && nums[i]==nums[i+1]){
continue;
}
if(nums[i] == start){
start++;
}else{
[Link](getRange(start, nums[i]-1));
if(nums[i]==Integer.MAX_VALUE){
return result;
}
start = nums[i]+1;
}
}
if(start<=upper){
[Link](getRange(start, upper));
}
return result;
}
private String getRange(int n1, int n2) {
return n1 == n2 ? [Link](n1) : [Link]("%d->%d" , n1, n2);
}
29 | 568
11 Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].
11.1 Analysis
The key to solve this problem is defining a Comparator first to sort the arraylist of Intevals.
11.2 Java Solution
public List<Interval> merge(List<Interval> intervals) {
if(intervals == null || [Link]()<=1){
return intervals;
}
[Link](intervals, [Link]((Interval itl)->[Link]));
List<Interval> result = new ArrayList<>();
Interval t = [Link](0);
for(int i=1; i<[Link](); i++){
Interval c = [Link](i);
if([Link] <= [Link]){
[Link] = [Link]([Link], [Link]);
}else{
[Link](t);
t = c;
}
}
[Link](t);
return result;
}
30 | 568
12 Insert Interval
Problem:
Given a set of non-overlapping & sorted intervals, insert a new interval into the intervals (merge if necessary).
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
12.1 Java Solution 1
When iterating over the list, there are three cases for the current range.
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
31 | 568