Skip to content

Commit a0f8a9d

Browse files
fishercoder1534fishercoder1534
committed
length of increasing subsequence using binary search
1 parent e07e906 commit a0f8a9d

File tree

2 files changed

+140
-100
lines changed

2 files changed

+140
-100
lines changed

‎Common/src/utils/CommonUtils.java

+107-99
Original file line numberDiff line numberDiff line change
@@ -8,53 +8,61 @@
88

99
public class CommonUtils {
1010

11-
private static final int DEFAULT_TREE_SIZE = 10;
12-
private static final int DEFAULT_UPPER_BOUND = 100;
13-
14-
public static void print(String message) {
15-
System.out.print(message);
16-
}
17-
18-
public static void print(int num) {
19-
System.out.print(num);
20-
}
21-
22-
public static void println(String message) {
23-
System.out.println(message);
24-
}
25-
26-
public static void println(int num) {
27-
System.out.println(num);
28-
}
29-
30-
public static void println() {
31-
System.out.println();
32-
}
33-
34-
//overloaded method to take only one argument
35-
public static List<Integer> randomIntArrayGenerator(int size) {
36-
return CommonUtils.randomIntArrayGenerator(size, DEFAULT_UPPER_BOUND);
37-
}
38-
39-
//overloaded method to take no argument
40-
public static List<Integer> randomIntArrayGenerator() {
41-
return CommonUtils.randomIntArrayGenerator(CommonUtils.DEFAULT_TREE_SIZE, DEFAULT_UPPER_BOUND);
42-
}
43-
44-
//this one has two other overloaded methods as above
45-
public static List<Integer> randomIntArrayGenerator(int size, int upperBound) {
46-
List<Integer> result = new ArrayList<Integer>();
47-
Random random = new Random();
48-
for (int i = 0; i < size; i++) {
49-
int randomInt = random.nextInt(upperBound);
50-
result.add(randomInt);
51-
print(String.valueOf(randomInt) + " ");
52-
}
53-
println();
54-
return result;
55-
}
56-
57-
//this one has two other overloaded methods as above
11+
private static final int DEFAULT_TREE_SIZE = 10;
12+
private static final int DEFAULT_UPPER_BOUND = 100;
13+
14+
public static void printArray(int[] nums) {
15+
for(int i : nums){
16+
System.out.print(i + ", ");
17+
}
18+
System.out.println();
19+
}
20+
21+
public static void print(String message) {
22+
System.out.print(message);
23+
}
24+
25+
public static void print(int num) {
26+
System.out.print(num);
27+
}
28+
29+
public static void println(String message) {
30+
System.out.println(message);
31+
}
32+
33+
public static void println(int num) {
34+
System.out.println(num);
35+
}
36+
37+
public static void println() {
38+
System.out.println();
39+
}
40+
41+
// overloaded method to take only one argument
42+
public static List<Integer> randomIntArrayGenerator(int size) {
43+
return CommonUtils.randomIntArrayGenerator(size, DEFAULT_UPPER_BOUND);
44+
}
45+
46+
// overloaded method to take no argument
47+
public static List<Integer> randomIntArrayGenerator() {
48+
return CommonUtils.randomIntArrayGenerator(CommonUtils.DEFAULT_TREE_SIZE,
49+
DEFAULT_UPPER_BOUND);
50+
}
51+
52+
// this one has two other overloaded methods as above
53+
public static List<Integer> randomIntArrayGenerator(int size, int upperBound) {
54+
List<Integer> result = new ArrayList<Integer>();
55+
Random random = new Random();
56+
for (int i = 0; i < size; i++) {
57+
int randomInt = random.nextInt(upperBound);
58+
result.add(randomInt);
59+
print(String.valueOf(randomInt) + " ");
60+
}
61+
println();
62+
return result;
63+
}
64+
65+
// this one has two other overloaded methods as above
5866
public static List<Integer> uniqueIntArrayGenerator(int size) {
5967
List<Integer> result = new ArrayList<Integer>();
6068
for (int i = 0; i < size; i++) {
@@ -64,59 +72,59 @@ public static List<Integer> uniqueIntArrayGenerator(int size) {
6472
return result;
6573
}
6674

67-
// @Notes(context = "I'm assuing only classes in this PACKAGE will call the following two methods, so just leave the modifier as default, i.e. no public, private, or protected.")
68-
public
69-
static void printWhitespaces(int count) {
70-
for (int i = 0; i < count; i++)
71-
System.out.print(" ");
72-
}
73-
74-
public static <T> boolean isAllElementsNull(List<T> list) {
75-
for (Object object : list) {
76-
if (object != null)
77-
return false;
78-
}
79-
80-
return true;
81-
}
82-
83-
/**
84-
* If you want to print the reversed list out, you need to return the
85-
* reversed list's head, which was the end node of the original node. using
86-
* the following function.
87-
*/
88-
public static ListNode reverseList(ListNode head) {
89-
if (head == null || head.next == null) {
90-
return head;
91-
}
92-
ListNode previous, current, next;
93-
previous = head;
94-
current = head.next;
95-
while (current != null) {
96-
next = current.next;
97-
current.next = previous;
98-
previous = current;
99-
current = next;
100-
}
101-
head.next = null;
102-
return previous;
103-
}
104-
105-
public static void printList(final ListNode head) {
106-
ListNode temp = head;
107-
System.out.println("--------------------------------------------");
108-
while (temp != null) {
109-
System.out.print(temp.val);
110-
temp = temp.next;
111-
if(temp != null) System.out.print("->");
112-
}
113-
System.out.println();
114-
}
115-
116-
public static void printMatrix(int[][] matrix) {
75+
// @Notes(context =
76+
// "I'm assuing only classes in this PACKAGE will call the following two methods, so just leave the modifier as default, i.e. no public, private, or protected.")
77+
public static void printWhitespaces(int count) {
78+
for (int i = 0; i < count; i++)
79+
System.out.print(" ");
80+
}
81+
82+
public static <T> boolean isAllElementsNull(List<T> list) {
83+
for (Object object : list) {
84+
if (object != null)
85+
return false;
86+
}
87+
88+
return true;
89+
}
90+
91+
/**
92+
* If you want to print the reversed list out, you need to return the reversed list's head,
93+
* which was the end node of the original node. using the following function.
94+
*/
95+
public static ListNode reverseList(ListNode head) {
96+
if (head == null || head.next == null) {
97+
return head;
98+
}
99+
ListNode previous, current, next;
100+
previous = head;
101+
current = head.next;
102+
while (current != null) {
103+
next = current.next;
104+
current.next = previous;
105+
previous = current;
106+
current = next;
107+
}
108+
head.next = null;
109+
return previous;
110+
}
111+
112+
public static void printList(final ListNode head) {
113+
ListNode temp = head;
114+
System.out.println("--------------------------------------------");
115+
while (temp != null) {
116+
System.out.print(temp.val);
117+
temp = temp.next;
118+
if (temp != null)
119+
System.out.print("->");
120+
}
121+
System.out.println();
122+
}
123+
124+
public static void printMatrix(int[][] matrix) {
117125
System.out.println("Matrix is: ");
118-
for(int i = 0; i < matrix.length; i++){
119-
for(int j = 0; j < matrix[0].length; j++){
126+
for (int i = 0; i < matrix.length; i++) {
127+
for (int j = 0; j < matrix[0].length; j++) {
120128
System.out.print(matrix[i][j] + "\t");
121129
}
122130
System.out.println();

‎MEDIUM/src/medium/LengthIncreasingSubsequence.java

+33-1
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package medium;
22

3+
import java.util.Arrays;
4+
35
import utils.CommonUtils;
46

57
/**300. Longest Increasing Subsequence QuestionEditorial Solution My Submissions
@@ -19,13 +21,43 @@ Your algorithm should run in O(n2) complexity.
1921
Credits:
2022
Special thanks to @pbrother for adding this problem and creating all test cases.*/
2123
public class LengthIncreasingSubsequence {
24+
25+
public int lengthOfLIS_using_binary_search_from_discuss(int[] nums) {
26+
/**Java doc for this Arrays.binarySearch method:
27+
* int java.util.Arrays.binarySearch(int[] a, int fromIndex, int toIndex, int key)
28+
29+
Searches a range of the specified array of ints for the specified value using the binary search algorithm. The range must be sorted (as by the sort(int [], int, int) method) prior to making this call. If it is not sorted, the results are undefined. If the range contains multiple elements with the specified value, there is no guarantee which one will be found.
30+
31+
Parameters:
32+
a the array to be searched
33+
fromIndex the index of the first element (inclusive) to be searched
34+
toIndex the index of the last element (exclusive) to be searched
35+
key the value to be searched for
36+
37+
Returns:
38+
index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element in the range greater than the key, or toIndex if all elements in the range are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.*/
39+
int[] dp = new int[nums.length];
40+
int len = 0;
41+
for(int x : nums){
42+
int i = Arrays.binarySearch(dp, 0, len, x);
43+
System.out.println("i = " + i + "\tx = " + x);
44+
if(i < 0) i = -(i+1);
45+
dp[i] = x;
46+
if(i == len) len++;
47+
}
48+
CommonUtils.printArray(nums);
49+
CommonUtils.printArray(dp);
50+
return len;
51+
}
52+
2253
public static void main(String...strings){
2354
LengthIncreasingSubsequence test = new LengthIncreasingSubsequence();
2455
int[] nums = new int[]{10, 9, 2, 5, 3, 7, 101, 18};
2556
// int[] nums = new int[]{10,9,2,5,3,4};
2657
// int[] nums = new int[]{1,3,6,7,9,4,10,5,6};
2758
// int[] nums = new int[]{18,55,66,2,3,54};
28-
System.out.println(test.lengthOfLIS(nums));
59+
// System.out.println(test.lengthOfLIS(nums));
60+
System.out.println(test.lengthOfLIS_using_binary_search_from_discuss(nums));
2961
}
3062

3163
/**This is the closest I got, passed all normal cases, made it to 22/23 test cases, but got TLE, as I expected,

0 commit comments

Comments
 (0)