Skip to content

Commit b5c9395

Browse files
fishercoder1534fishercoder1534
committed
add 1966
1 parent 22c8dd1 commit b5c9395

File tree

3 files changed

+145
-0
lines changed

3 files changed

+145
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,7 @@ _If you like this project, please leave me a star._ ★
4444
|1971|[Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1971.java) ||Easy|BFS, DFS, Graph|
4545
|1968|[Array With Elements Not Equal to Average of Neighbors](https://leetcode.com/problems/array-with-elements-not-equal-to-average-of-neighbors/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1968.java) ||Medium||
4646
|1967|[Number of Strings That Appear as Substrings in Word](https://leetcode.com/problems/number-of-strings-that-appear-as-substrings-in-word/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1967.java) ||Easy||
47+
|1966|[Binary Searchable Numbers in an Unsorted Array](https://leetcode.com/problems/binary-searchable-numbers-in-an-unsorted-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1966.java) ||Medium|Array, Binary Search|
4748
|1961|[Check If String Is a Prefix of Array](https://leetcode.com/problems/check-if-string-is-a-prefix-of-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1961.java) ||Easy||
4849
|1957|[Delete Characters to Make Fancy String](https://leetcode.com/problems/delete-characters-to-make-fancy-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1957.java) ||Easy|String|
4950
|1952|[Three Divisors](https://leetcode.com/problems/three-divisors/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1952.java) ||Easy||

‎src/main/java/com/fishercoder/solutions/_1966.java

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.Deque;
4+
import java.util.LinkedList;
5+
6+
public class _1966 {
7+
public static class Solution1 {
8+
/**
9+
* Brute force: this ends in TLE on LeetCode.
10+
* The idea is: for every single number in the array, check if there's any number on its right side that's smaller than it
11+
* and if there's any number on its left side that's bigger than it.
12+
* If so, based on binary search, if that number gets picked as a pivot for the next search, then this number might not be found.
13+
*/
14+
public int binarySearchableNumbers(int[] nums) {
15+
int ans = 0;
16+
for (int i = 0; i < nums.length; i++) {
17+
int j = i + 1;
18+
for (; j < nums.length; j++) {
19+
if (nums[j] < nums[i]) {
20+
break;
21+
}
22+
}
23+
if (j == nums.length) {
24+
int k = i - 1;
25+
for (; k >= 0; k--) {
26+
if (nums[i] < nums[k]) {
27+
break;
28+
}
29+
}
30+
if (k <= 0) {
31+
ans++;
32+
}
33+
}
34+
}
35+
return ans;
36+
}
37+
}
38+
39+
public static class Solution2 {
40+
/**
41+
* My completely original solution.
42+
*/
43+
public int binarySearchableNumbers(int[] nums) {
44+
int ans = 0;
45+
int[] maxLeft = new int[nums.length];
46+
for (int i = 0; i < nums.length; i++) {
47+
maxLeft[i] = i == 0 ? nums[i] : Math.max(nums[i], maxLeft[i - 1]);
48+
}
49+
int[] minRight = new int[nums.length];
50+
for (int i = nums.length - 1; i >= 0; i--) {
51+
minRight[i] = i + 1 == nums.length ? nums[i] : Math.min(minRight[i + 1], nums[i]);
52+
}
53+
for (int i = 0; i < nums.length; i++) {
54+
if (nums[i] >= maxLeft[i] && nums[i] <= minRight[i]) {
55+
ans++;
56+
}
57+
}
58+
return ans;
59+
}
60+
}
61+
62+
public static class Solution3 {
63+
/**
64+
* Using monotonic stack:
65+
* 1. we only add the ones that are greater than those already on the stack onto the stack.
66+
* 2. if the existing ones on the stack are greater than the current one,
67+
* pop them off because they won't be found based on binary search, as a smaller element is on their right side.
68+
*/
69+
public int binarySearchableNumbers(int[] nums) {
70+
Deque<Integer> stack = new LinkedList<>();
71+
int maxLeft = Integer.MIN_VALUE;
72+
for (int num : nums) {
73+
while (!stack.isEmpty() && stack.peekLast() > num) {
74+
stack.pollLast();
75+
}
76+
if (num >= maxLeft) {
77+
stack.addLast(num);
78+
}
79+
maxLeft = Math.max(maxLeft, num);
80+
}
81+
return stack.size();
82+
}
83+
}
84+
}

‎src/test/java/com/fishercoder/_1966Test.java

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._1966;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
public class _1966Test {
10+
private static _1966.Solution1 solution1;
11+
private static _1966.Solution2 solution2;
12+
private static _1966.Solution3 solution3;
13+
private static int[] nums;
14+
private static int expected;
15+
16+
@BeforeClass
17+
public static void setup() {
18+
solution1 = new _1966.Solution1();
19+
solution2 = new _1966.Solution2();
20+
solution3 = new _1966.Solution3();
21+
}
22+
23+
@Test
24+
public void test1() {
25+
nums = new int[]{7};
26+
expected = 1;
27+
assertEquals(expected, solution1.binarySearchableNumbers(nums));
28+
assertEquals(expected, solution2.binarySearchableNumbers(nums));
29+
assertEquals(expected, solution3.binarySearchableNumbers(nums));
30+
}
31+
32+
@Test
33+
public void test2() {
34+
nums = new int[]{-1, 5, 2};
35+
expected = 1;
36+
assertEquals(expected, solution1.binarySearchableNumbers(nums));
37+
assertEquals(expected, solution2.binarySearchableNumbers(nums));
38+
assertEquals(expected, solution3.binarySearchableNumbers(nums));
39+
}
40+
41+
@Test
42+
public void test3() {
43+
/**This is to answer the follow-up question, what if duplicates are allowed in the input*/
44+
nums = new int[]{-1, -1, 5, 2};
45+
expected = 2;
46+
assertEquals(expected, solution1.binarySearchableNumbers(nums));
47+
assertEquals(expected, solution2.binarySearchableNumbers(nums));
48+
assertEquals(expected, solution3.binarySearchableNumbers(nums));
49+
}
50+
51+
@Test
52+
public void test4() {
53+
/**This is to answer the follow-up question, what if duplicates are allowed in the input*/
54+
nums = new int[]{-1, -1, 5, 2, 2, 5};
55+
expected = 3;
56+
assertEquals(expected, solution1.binarySearchableNumbers(nums));
57+
assertEquals(expected, solution2.binarySearchableNumbers(nums));
58+
assertEquals(expected, solution3.binarySearchableNumbers(nums));
59+
}
60+
}

0 commit comments

Comments
 (0)