Skip to content

Commit 936861c

Browse files
github-actionsgithub-actions
github-actions
authored and
github-actions
committed
Formatted with Google Java Formatter
1 parent ecefcf3 commit 936861c

File tree

2 files changed

+170
-170
lines changed

2 files changed

+170
-170
lines changed

‎Misc/RangeInSortedArray.java

Lines changed: 67 additions & 67 deletions
Original file line numberDiff line numberDiff line change
@@ -4,79 +4,79 @@
44

55
public class RangeInSortedArray {
66

7-
public static void main(String[] args) {
8-
// Testcases
9-
assert Arrays.equals(sortedRange(new int[] {1, 2, 3, 3, 3, 4, 5}, 3), new int[] {2, 4});
10-
assert Arrays.equals(sortedRange(new int[] {1, 2, 3, 3, 3, 4, 5}, 4), new int[] {5, 5});
11-
assert Arrays.equals(sortedRange(new int[] {0, 1, 2}, 3), new int[] {-1, -1});
12-
}
7+
public static void main(String[] args) {
8+
// Testcases
9+
assert Arrays.equals(sortedRange(new int[] {1, 2, 3, 3, 3, 4, 5}, 3), new int[] {2, 4});
10+
assert Arrays.equals(sortedRange(new int[] {1, 2, 3, 3, 3, 4, 5}, 4), new int[] {5, 5});
11+
assert Arrays.equals(sortedRange(new int[] {0, 1, 2}, 3), new int[] {-1, -1});
12+
}
1313

14-
// Get the 1st and last occurrence index of a number 'key' in a non-decreasing array 'nums'
15-
// Gives [-1, -1] in case element doesn't exist in array
16-
public static int[] sortedRange(int[] nums, int key) {
17-
int[] range = new int[] {-1, -1};
18-
alteredBinSearchIter(nums, key, 0, nums.length - 1, range, true);
19-
alteredBinSearchIter(nums, key, 0, nums.length - 1, range, false);
20-
return range;
21-
}
14+
// Get the 1st and last occurrence index of a number 'key' in a non-decreasing array 'nums'
15+
// Gives [-1, -1] in case element doesn't exist in array
16+
public static int[] sortedRange(int[] nums, int key) {
17+
int[] range = new int[] {-1, -1};
18+
alteredBinSearchIter(nums, key, 0, nums.length - 1, range, true);
19+
alteredBinSearchIter(nums, key, 0, nums.length - 1, range, false);
20+
return range;
21+
}
2222

23-
// Recursive altered binary search which searches for leftmost as well as rightmost occurrence of
24-
// 'key'
25-
public static void alteredBinSearch(
26-
int[] nums, int key, int left, int right, int[] range, boolean goLeft) {
27-
if (left > right) return;
28-
int mid = (left + right) / 2;
29-
if (nums[mid] > key) alteredBinSearch(nums, key, left, mid - 1, range, goLeft);
30-
else if (nums[mid] < key) alteredBinSearch(nums, key, mid + 1, right, range, goLeft);
31-
else {
32-
if (goLeft) {
33-
if (mid == 0 || nums[mid - 1] != key) range[0] = mid;
34-
else alteredBinSearch(nums, key, left, mid - 1, range, goLeft);
35-
} else {
36-
if (mid == nums.length - 1 || nums[mid + 1] != key) range[1] = mid;
37-
else alteredBinSearch(nums, key, mid + 1, right, range, goLeft);
38-
}
39-
}
23+
// Recursive altered binary search which searches for leftmost as well as rightmost occurrence of
24+
// 'key'
25+
public static void alteredBinSearch(
26+
int[] nums, int key, int left, int right, int[] range, boolean goLeft) {
27+
if (left > right) return;
28+
int mid = (left + right) / 2;
29+
if (nums[mid] > key) alteredBinSearch(nums, key, left, mid - 1, range, goLeft);
30+
else if (nums[mid] < key) alteredBinSearch(nums, key, mid + 1, right, range, goLeft);
31+
else {
32+
if (goLeft) {
33+
if (mid == 0 || nums[mid - 1] != key) range[0] = mid;
34+
else alteredBinSearch(nums, key, left, mid - 1, range, goLeft);
35+
} else {
36+
if (mid == nums.length - 1 || nums[mid + 1] != key) range[1] = mid;
37+
else alteredBinSearch(nums, key, mid + 1, right, range, goLeft);
38+
}
4039
}
40+
}
4141

42-
// Iterative altered binary search which searches for leftmost as well as rightmost occurrence of
43-
// 'key'
44-
public static void alteredBinSearchIter(
45-
int[] nums, int key, int left, int right, int[] range, boolean goLeft) {
46-
while (left <= right) {
47-
int mid = (left + right) / 2;
48-
if (nums[mid] > key) right = mid - 1;
49-
else if (nums[mid] < key) left = mid + 1;
50-
else {
51-
if (goLeft) {
52-
if (mid == 0 || nums[mid - 1] != key) {
53-
range[0] = mid;
54-
return;
55-
} else right = mid - 1;
56-
} else {
57-
if (mid == nums.length - 1 || nums[mid + 1] != key) {
58-
range[1] = mid;
59-
return;
60-
} else left = mid + 1;
61-
}
62-
}
42+
// Iterative altered binary search which searches for leftmost as well as rightmost occurrence of
43+
// 'key'
44+
public static void alteredBinSearchIter(
45+
int[] nums, int key, int left, int right, int[] range, boolean goLeft) {
46+
while (left <= right) {
47+
int mid = (left + right) / 2;
48+
if (nums[mid] > key) right = mid - 1;
49+
else if (nums[mid] < key) left = mid + 1;
50+
else {
51+
if (goLeft) {
52+
if (mid == 0 || nums[mid - 1] != key) {
53+
range[0] = mid;
54+
return;
55+
} else right = mid - 1;
56+
} else {
57+
if (mid == nums.length - 1 || nums[mid + 1] != key) {
58+
range[1] = mid;
59+
return;
60+
} else left = mid + 1;
6361
}
62+
}
6463
}
64+
}
6565

66-
public static int getCountLessThan(int[] nums, int key) {
67-
return getLessThan(nums, key, 0, nums.length - 1);
68-
}
66+
public static int getCountLessThan(int[] nums, int key) {
67+
return getLessThan(nums, key, 0, nums.length - 1);
68+
}
6969

70-
public static int getLessThan(int[] nums, int key, int left, int right) {
71-
int count = 0;
72-
while (left <= right) {
73-
int mid = (left + right) / 2;
74-
if (nums[mid] > key) right = mid - 1;
75-
else if (nums[mid] <= key) {
76-
count = mid + 1; // Atleast mid+1 elements exist which are <= key
77-
left = mid + 1;
78-
}
79-
}
80-
return count;
70+
public static int getLessThan(int[] nums, int key, int left, int right) {
71+
int count = 0;
72+
while (left <= right) {
73+
int mid = (left + right) / 2;
74+
if (nums[mid] > key) right = mid - 1;
75+
else if (nums[mid] <= key) {
76+
count = mid + 1; // Atleast mid+1 elements exist which are <= key
77+
left = mid + 1;
78+
}
8179
}
82-
}
80+
return count;
81+
}
82+
}

‎Misc/WordBoggle.java

Lines changed: 103 additions & 103 deletions
Original file line numberDiff line numberDiff line change
@@ -2,129 +2,129 @@
22

33
public class WordBoggle {
44

5-
/**
6-
* O(nm * 8^s + ws) time where n=width of boggle board, m=height of boggle board, s=length of
7-
* longest word in string array, w= length of string array, 8 is due to 8 explorable neighbours
8-
* O(nm + ws) space.
9-
*/
10-
public static List<String> boggleBoard(char[][] board, String[] words) {
11-
Trie trie = new Trie();
12-
for (String word : words) trie.add(word);
13-
Set<String> finalWords = new HashSet<>();
14-
boolean[][] visited = new boolean[board.length][board.length];
15-
for (int i = 0; i < board.length; i++)
16-
for (int j = 0; j < board[i].length; j++)
17-
explore(i, j, board, trie.root, visited, finalWords);
18-
return new ArrayList<>(finalWords);
5+
/**
6+
* O(nm * 8^s + ws) time where n=width of boggle board, m=height of boggle board, s=length of
7+
* longest word in string array, w= length of string array, 8 is due to 8 explorable neighbours
8+
* O(nm + ws) space.
9+
*/
10+
public static List<String> boggleBoard(char[][] board, String[] words) {
11+
Trie trie = new Trie();
12+
for (String word : words) trie.add(word);
13+
Set<String> finalWords = new HashSet<>();
14+
boolean[][] visited = new boolean[board.length][board.length];
15+
for (int i = 0; i < board.length; i++)
16+
for (int j = 0; j < board[i].length; j++)
17+
explore(i, j, board, trie.root, visited, finalWords);
18+
return new ArrayList<>(finalWords);
19+
}
20+
21+
public static void main(String[] args) {
22+
// Testcase
23+
List<String> ans =
24+
new ArrayList<>(
25+
Arrays.asList("a", "boggle", "this", "NOTRE_PEATED", "is", "simple", "board"));
26+
assert (boggleBoard(
27+
new char[][] {
28+
{'t', 'h', 'i', 's', 'i', 's', 'a'},
29+
{'s', 'i', 'm', 'p', 'l', 'e', 'x'},
30+
{'b', 'x', 'x', 'x', 'x', 'e', 'b'},
31+
{'x', 'o', 'g', 'g', 'l', 'x', 'o'},
32+
{'x', 'x', 'x', 'D', 'T', 'r', 'a'},
33+
{'R', 'E', 'P', 'E', 'A', 'd', 'x'},
34+
{'x', 'x', 'x', 'x', 'x', 'x', 'x'},
35+
{'N', 'O', 'T', 'R', 'E', '_', 'P'},
36+
{'x', 'x', 'D', 'E', 'T', 'A', 'E'},
37+
},
38+
new String[] {
39+
"this",
40+
"is",
41+
"not",
42+
"a",
43+
"simple",
44+
"test",
45+
"boggle",
46+
"board",
47+
"REPEATED",
48+
"NOTRE_PEATED",
49+
})
50+
.equals(ans));
51+
}
52+
53+
public static void explore(
54+
int i,
55+
int j,
56+
char[][] board,
57+
TrieNode trieNode,
58+
boolean[][] visited,
59+
Set<String> finalWords) {
60+
if (visited[i][j]) return;
61+
62+
char letter = board[i][j];
63+
if (!trieNode.children.containsKey(letter)) {
64+
return;
1965
}
66+
visited[i][j] = true;
67+
trieNode = trieNode.children.get(letter);
68+
if (trieNode.children.containsKey('*')) finalWords.add(trieNode.word);
2069

21-
public static void main(String[] args) {
22-
// Testcase
23-
List<String> ans =
24-
new ArrayList<>(
25-
Arrays.asList("a", "boggle", "this", "NOTRE_PEATED", "is", "simple", "board"));
26-
assert (boggleBoard(
27-
new char[][] {
28-
{'t', 'h', 'i', 's', 'i', 's', 'a'},
29-
{'s', 'i', 'm', 'p', 'l', 'e', 'x'},
30-
{'b', 'x', 'x', 'x', 'x', 'e', 'b'},
31-
{'x', 'o', 'g', 'g', 'l', 'x', 'o'},
32-
{'x', 'x', 'x', 'D', 'T', 'r', 'a'},
33-
{'R', 'E', 'P', 'E', 'A', 'd', 'x'},
34-
{'x', 'x', 'x', 'x', 'x', 'x', 'x'},
35-
{'N', 'O', 'T', 'R', 'E', '_', 'P'},
36-
{'x', 'x', 'D', 'E', 'T', 'A', 'E'},
37-
},
38-
new String[] {
39-
"this",
40-
"is",
41-
"not",
42-
"a",
43-
"simple",
44-
"test",
45-
"boggle",
46-
"board",
47-
"REPEATED",
48-
"NOTRE_PEATED",
49-
})
50-
.equals(ans));
51-
}
70+
List<Integer[]> neighbors = getNeighbors(i, j, board);
71+
for (Integer[] neighbor : neighbors)
72+
explore(neighbor[0], neighbor[1], board, trieNode, visited, finalWords);
5273

53-
public static void explore(
54-
int i,
55-
int j,
56-
char[][] board,
57-
TrieNode trieNode,
58-
boolean[][] visited,
59-
Set<String> finalWords) {
60-
if (visited[i][j]) return;
61-
62-
char letter = board[i][j];
63-
if (!trieNode.children.containsKey(letter)) {
64-
return;
65-
}
66-
visited[i][j] = true;
67-
trieNode = trieNode.children.get(letter);
68-
if (trieNode.children.containsKey('*')) finalWords.add(trieNode.word);
69-
70-
List<Integer[]> neighbors = getNeighbors(i, j, board);
71-
for (Integer[] neighbor : neighbors)
72-
explore(neighbor[0], neighbor[1], board, trieNode, visited, finalWords);
73-
74-
visited[i][j] = false;
75-
}
74+
visited[i][j] = false;
75+
}
7676

77-
public static List<Integer[]> getNeighbors(int i, int j, char[][] board) {
78-
List<Integer[]> neighbors = new ArrayList<>();
79-
if (i > 0 && j > 0) neighbors.add(new Integer[] {i - 1, j - 1});
77+
public static List<Integer[]> getNeighbors(int i, int j, char[][] board) {
78+
List<Integer[]> neighbors = new ArrayList<>();
79+
if (i > 0 && j > 0) neighbors.add(new Integer[] {i - 1, j - 1});
8080

81-
if (i > 0 && j < board[0].length - 1) neighbors.add(new Integer[] {i - 1, j + 1});
81+
if (i > 0 && j < board[0].length - 1) neighbors.add(new Integer[] {i - 1, j + 1});
8282

83-
if (i < board.length - 1 && j < board[0].length - 1)
84-
neighbors.add(new Integer[] {i + 1, j + 1});
83+
if (i < board.length - 1 && j < board[0].length - 1)
84+
neighbors.add(new Integer[] {i + 1, j + 1});
8585

86-
if (i < board.length - 1 && j > 0) neighbors.add(new Integer[] {i + 1, j - 1});
86+
if (i < board.length - 1 && j > 0) neighbors.add(new Integer[] {i + 1, j - 1});
8787

88-
if (i > 0) neighbors.add(new Integer[] {i - 1, j});
88+
if (i > 0) neighbors.add(new Integer[] {i - 1, j});
8989

90-
if (i < board.length - 1) neighbors.add(new Integer[] {i + 1, j});
90+
if (i < board.length - 1) neighbors.add(new Integer[] {i + 1, j});
9191

92-
if (j > 0) neighbors.add(new Integer[] {i, j - 1});
92+
if (j > 0) neighbors.add(new Integer[] {i, j - 1});
9393

94-
if (j < board[0].length - 1) neighbors.add(new Integer[] {i, j + 1});
94+
if (j < board[0].length - 1) neighbors.add(new Integer[] {i, j + 1});
9595

96-
return neighbors;
97-
}
96+
return neighbors;
97+
}
9898
}
9999

100100
// Trie used to optimize string search
101101
class TrieNode {
102102

103-
Map<Character, TrieNode> children = new HashMap<>();
104-
String word = "";
103+
Map<Character, TrieNode> children = new HashMap<>();
104+
String word = "";
105105
}
106106

107107
class Trie {
108108

109-
TrieNode root;
110-
char endSymbol;
111-
112-
public Trie() {
113-
this.root = new TrieNode();
114-
this.endSymbol = '*';
115-
}
116-
117-
public void add(String str) {
118-
TrieNode node = this.root;
119-
for (int i = 0; i < str.length(); i++) {
120-
char letter = str.charAt(i);
121-
if (!node.children.containsKey(letter)) {
122-
TrieNode newNode = new TrieNode();
123-
node.children.put(letter, newNode);
124-
}
125-
node = node.children.get(letter);
126-
}
127-
node.children.put(this.endSymbol, null);
128-
node.word = str;
109+
TrieNode root;
110+
char endSymbol;
111+
112+
public Trie() {
113+
this.root = new TrieNode();
114+
this.endSymbol = '*';
115+
}
116+
117+
public void add(String str) {
118+
TrieNode node = this.root;
119+
for (int i = 0; i < str.length(); i++) {
120+
char letter = str.charAt(i);
121+
if (!node.children.containsKey(letter)) {
122+
TrieNode newNode = new TrieNode();
123+
node.children.put(letter, newNode);
124+
}
125+
node = node.children.get(letter);
129126
}
127+
node.children.put(this.endSymbol, null);
128+
node.word = str;
129+
}
130130
}

0 commit comments

Comments
 (0)