Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 66268ec

Browse filesBrowse files
javadevjavadev
authored
Added tasks 3285-3292
1 parent 1c7c296 commit 66268ec
Copy full SHA for 66268ec

File tree

24 files changed

+1012
-0
lines changed
Filter options

24 files changed

+1012
-0
lines changed

‎src/main/kotlin/g3201_3300/s3285_find_indices_of_stable_mountains/Solution.kt

Copy file name to clipboard
+16Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
package g3201_3300.s3285_find_indices_of_stable_mountains
2+
3+
// #Easy #Array #2024_09_17_Time_195_ms_(92.68%)_Space_37.5_MB_(48.78%)
4+
5+
class Solution {
6+
fun stableMountains(height: IntArray, threshold: Int): List<Int> {
7+
val n = height.size
8+
val list: MutableList<Int> = mutableListOf()
9+
for (i in 0 until n - 1) {
10+
if (height[i] > threshold) {
11+
list.add(i + 1)
12+
}
13+
}
14+
return list
15+
}
16+
}

‎src/main/kotlin/g3201_3300/s3285_find_indices_of_stable_mountains/readme.md

Copy file name to clipboard
+38Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
3285\. Find Indices of Stable Mountains
2+
3+
Easy
4+
5+
There are `n` mountains in a row, and each mountain has a height. You are given an integer array `height` where `height[i]` represents the height of mountain `i`, and an integer `threshold`.
6+
7+
A mountain is called **stable** if the mountain just before it (**if it exists**) has a height **strictly greater** than `threshold`. **Note** that mountain 0 is **not** stable.
8+
9+
Return an array containing the indices of _all_ **stable** mountains in **any** order.
10+
11+
**Example 1:**
12+
13+
**Input:** height = [1,2,3,4,5], threshold = 2
14+
15+
**Output:** [3,4]
16+
17+
**Explanation:**
18+
19+
* Mountain 3 is stable because `height[2] == 3` is greater than `threshold == 2`.
20+
* Mountain 4 is stable because `height[3] == 4` is greater than `threshold == 2`.
21+
22+
**Example 2:**
23+
24+
**Input:** height = [10,1,10,1,10], threshold = 3
25+
26+
**Output:** [1,3]
27+
28+
**Example 3:**
29+
30+
**Input:** height = [10,1,10,1,10], threshold = 10
31+
32+
**Output:** []
33+
34+
**Constraints:**
35+
36+
* `2 <= n == height.length <= 100`
37+
* `1 <= height[i] <= 100`
38+
* `1 <= threshold <= 100`

‎src/main/kotlin/g3201_3300/s3286_find_a_safe_walk_through_a_grid/Solution.kt

Copy file name to clipboard
+49Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package g3201_3300.s3286_find_a_safe_walk_through_a_grid
2+
3+
// #Medium #Array #Breadth_First_Search #Matrix #Heap_Priority_Queue #Graph #Shortest_Path
4+
// #2024_09_17_Time_357_ms_(48.28%)_Space_48.2_MB_(58.62%)
5+
6+
import java.util.LinkedList
7+
import java.util.Objects
8+
import java.util.Queue
9+
10+
class Solution {
11+
fun findSafeWalk(grid: List<List<Int>>, health: Int): Boolean {
12+
val n = grid.size
13+
val m = grid[0].size
14+
val dr = intArrayOf(0, 0, 1, -1)
15+
val dc = intArrayOf(1, -1, 0, 0)
16+
val visited = Array<Array<BooleanArray>?>(n) { Array<BooleanArray>(m) { BooleanArray(health + 1) } }
17+
val bfs: Queue<IntArray?> = LinkedList<IntArray>()
18+
bfs.add(intArrayOf(0, 0, health - grid[0][0]))
19+
visited[0]!![0][health - grid[0][0]] = true
20+
while (bfs.isNotEmpty()) {
21+
var size = bfs.size
22+
while (size-- > 0) {
23+
val currNode = bfs.poll()
24+
val r = Objects.requireNonNull<IntArray>(currNode)[0]
25+
val c = currNode!![1]
26+
val h = currNode[2]
27+
if (r == n - 1 && c == m - 1 && h > 0) {
28+
return true
29+
}
30+
for (k in 0..3) {
31+
val nr = r + dr[k]
32+
val nc = c + dc[k]
33+
if (isValidMove(nr, nc, n, m)) {
34+
val nh: Int = h - grid[nr][nc]
35+
if (nh >= 0 && !visited[nr]!![nc][nh]) {
36+
visited[nr]!![nc][nh] = true
37+
bfs.add(intArrayOf(nr, nc, nh))
38+
}
39+
}
40+
}
41+
}
42+
}
43+
return false
44+
}
45+
46+
private fun isValidMove(r: Int, c: Int, n: Int, m: Int): Boolean {
47+
return r >= 0 && c >= 0 && r < n && c < m
48+
}
49+
}

‎src/main/kotlin/g3201_3300/s3286_find_a_safe_walk_through_a_grid/readme.md

Copy file name to clipboard
+60Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
3286\. Find a Safe Walk Through a Grid
2+
3+
Medium
4+
5+
You are given an `m x n` binary matrix `grid` and an integer `health`.
6+
7+
You start on the upper-left corner `(0, 0)` and would like to get to the lower-right corner `(m - 1, n - 1)`.
8+
9+
You can move up, down, left, or right from one cell to another adjacent cell as long as your health _remains_ **positive**.
10+
11+
Cells `(i, j)` with `grid[i][j] = 1` are considered **unsafe** and reduce your health by 1.
12+
13+
Return `true` if you can reach the final cell with a health value of 1 or more, and `false` otherwise.
14+
15+
**Example 1:**
16+
17+
**Input:** grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1
18+
19+
**Output:** true
20+
21+
**Explanation:**
22+
23+
The final cell can be reached safely by walking along the gray cells below.
24+
25+
![](https://assets.leetcode.com/uploads/2024/08/04/3868_examples_1drawio.png)
26+
27+
**Example 2:**
28+
29+
**Input:** grid = [[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health = 3
30+
31+
**Output:** false
32+
33+
**Explanation:**
34+
35+
A minimum of 4 health points is needed to reach the final cell safely.
36+
37+
![](https://assets.leetcode.com/uploads/2024/08/04/3868_examples_2drawio.png)
38+
39+
**Example 3:**
40+
41+
**Input:** grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5
42+
43+
**Output:** true
44+
45+
**Explanation:**
46+
47+
The final cell can be reached safely by walking along the gray cells below.
48+
49+
![](https://assets.leetcode.com/uploads/2024/08/04/3868_examples_3drawio.png)
50+
51+
Any path that does not go through the cell `(1, 1)` is unsafe since your health will drop to 0 when reaching the final cell.
52+
53+
**Constraints:**
54+
55+
* `m == grid.length`
56+
* `n == grid[i].length`
57+
* `1 <= m, n <= 50`
58+
* `2 <= m * n`
59+
* `1 <= health <= m + n`
60+
* `grid[i][j]` is either 0 or 1.

‎src/main/kotlin/g3201_3300/s3287_find_the_maximum_sequence_value_of_array/Solution.kt

Copy file name to clipboard
+50Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package g3201_3300.s3287_find_the_maximum_sequence_value_of_array
2+
3+
// #Hard #Array #Dynamic_Programming #Bit_Manipulation
4+
// #2024_09_17_Time_2893_ms_(33.33%)_Space_290.4_MB_(33.33%)
5+
6+
import kotlin.math.max
7+
8+
class Solution {
9+
fun maxValue(nums: IntArray, k: Int): Int {
10+
val n = nums.size
11+
val left: Array<Array<MutableSet<Int>>> =
12+
Array<Array<MutableSet<Int>>>(n) { Array<MutableSet<Int>>(k + 1) { mutableSetOf() } }
13+
val right: Array<Array<MutableSet<Int>>> =
14+
Array<Array<MutableSet<Int>>>(n) { Array<MutableSet<Int>>(k + 1) { mutableSetOf() } }
15+
left[0][0].add(0)
16+
left[0][1].add(nums[0])
17+
for (i in 1 until n - k) {
18+
left[i][0].add(0)
19+
for (j in 1..k) {
20+
left[i][j].addAll(left[i - 1][j])
21+
for (v in left[i - 1][j - 1]) {
22+
left[i][j].add(v or nums[i])
23+
}
24+
}
25+
}
26+
right[n - 1][0].add(0)
27+
right[n - 1][1].add(nums[n - 1])
28+
var result = 0
29+
if (k == 1) {
30+
for (l in left[n - 2][k]) {
31+
result = max(result, (l xor nums[n - 1]))
32+
}
33+
}
34+
for (i in n - 2 downTo k) {
35+
right[i][0].add(0)
36+
for (j in 1..k) {
37+
right[i][j].addAll(right[i + 1][j])
38+
for (v in right[i + 1][j - 1]) {
39+
right[i][j].add(v or nums[i])
40+
}
41+
}
42+
for (l in left[i - 1][k]) {
43+
for (r in right[i][k]) {
44+
result = max(result, (l xor r))
45+
}
46+
}
47+
}
48+
return result
49+
}
50+
}

‎src/main/kotlin/g3201_3300/s3287_find_the_maximum_sequence_value_of_array/readme.md

Copy file name to clipboard
+37Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
3287\. Find the Maximum Sequence Value of Array
2+
3+
Hard
4+
5+
You are given an integer array `nums` and a **positive** integer `k`.
6+
7+
The **value** of a sequence `seq` of size `2 * x` is defined as:
8+
9+
* `(seq[0] OR seq[1] OR ... OR seq[x - 1]) XOR (seq[x] OR seq[x + 1] OR ... OR seq[2 * x - 1])`.
10+
11+
Return the **maximum** **value** of any subsequence of `nums` having size `2 * k`.
12+
13+
**Example 1:**
14+
15+
**Input:** nums = [2,6,7], k = 1
16+
17+
**Output:** 5
18+
19+
**Explanation:**
20+
21+
The subsequence `[2, 7]` has the maximum value of `2 XOR 7 = 5`.
22+
23+
**Example 2:**
24+
25+
**Input:** nums = [4,2,5,6,7], k = 2
26+
27+
**Output:** 2
28+
29+
**Explanation:**
30+
31+
The subsequence `[4, 5, 6, 7]` has the maximum value of `(4 OR 5) XOR (6 OR 7) = 2`.
32+
33+
**Constraints:**
34+
35+
* `2 <= nums.length <= 400`
36+
* <code>1 <= nums[i] < 2<sup>7</sup></code>
37+
* `1 <= k <= nums.length / 2`

‎src/main/kotlin/g3201_3300/s3288_length_of_the_longest_increasing_path/Solution.kt

Copy file name to clipboard
+71Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
package g3201_3300.s3288_length_of_the_longest_increasing_path
2+
3+
// #Hard #Array #Sorting #Binary_Search #2024_09_17_Time_984_ms_(83.33%)_Space_147.1_MB_(16.67%)
4+
5+
import java.util.ArrayList
6+
import java.util.Comparator
7+
8+
class Solution {
9+
fun maxPathLength(coordinates: Array<IntArray>, k: Int): Int {
10+
val upper: MutableList<IntArray> = ArrayList<IntArray>()
11+
val lower: MutableList<IntArray> = ArrayList<IntArray>()
12+
for (pair in coordinates) {
13+
if (pair[0] > coordinates[k][0] && pair[1] > coordinates[k][1]) {
14+
upper.add(pair)
15+
}
16+
if (pair[0] < coordinates[k][0] && pair[1] < coordinates[k][1]) {
17+
lower.add(pair)
18+
}
19+
}
20+
upper.sortWith(
21+
Comparator { a: IntArray, b: IntArray ->
22+
if (a[0] == b[0]) {
23+
b[1] - a[1]
24+
} else {
25+
a[0] - b[0]
26+
}
27+
}
28+
)
29+
lower.sortWith(
30+
Comparator { a: IntArray, b: IntArray ->
31+
if (a[0] == b[0]) {
32+
b[1] - a[1]
33+
} else {
34+
a[0] - b[0]
35+
}
36+
}
37+
)
38+
return longestIncreasingLength(upper) + longestIncreasingLength(lower) + 1
39+
}
40+
41+
private fun longestIncreasingLength(array: List<IntArray>): Int {
42+
val list: MutableList<Int?> = ArrayList<Int?>()
43+
for (pair in array) {
44+
val m = list.size
45+
if (m == 0 || list[m - 1]!! < pair[1]) {
46+
list.add(pair[1])
47+
} else {
48+
val idx = binarySearch(list, pair[1])
49+
list[idx] = pair[1]
50+
}
51+
}
52+
return list.size
53+
}
54+
55+
private fun binarySearch(list: List<Int?>, target: Int): Int {
56+
val n = list.size
57+
var left = 0
58+
var right = n - 1
59+
while (left < right) {
60+
val mid = (left + right) / 2
61+
if (list[mid] == target) {
62+
return mid
63+
} else if (list[mid]!! > target) {
64+
right = mid
65+
} else {
66+
left = mid + 1
67+
}
68+
}
69+
return left
70+
}
71+
}

‎src/main/kotlin/g3201_3300/s3288_length_of_the_longest_increasing_path/readme.md

Copy file name to clipboard
+42Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
3288\. Length of the Longest Increasing Path
2+
3+
Hard
4+
5+
You are given a 2D array of integers `coordinates` of length `n` and an integer `k`, where `0 <= k < n`.
6+
7+
<code>coordinates[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> indicates the point <code>(x<sub>i</sub>, y<sub>i</sub>)</code> in a 2D plane.
8+
9+
An **increasing path** of length `m` is defined as a list of points <code>(x<sub>1</sub>, y<sub>1</sub>)</code>, <code>(x<sub>2</sub>, y<sub>2</sub>)</code>, <code>(x<sub>3</sub>, y<sub>3</sub>)</code>, ..., <code>(x<sub>m</sub>, y<sub>m</sub>)</code> such that:
10+
11+
* <code>x<sub>i</sub> < x<sub>i + 1</sub></code> and <code>y<sub>i</sub> < y<sub>i + 1</sub></code> for all `i` where `1 <= i < m`.
12+
* <code>(x<sub>i</sub>, y<sub>i</sub>)</code> is in the given coordinates for all `i` where `1 <= i <= m`.
13+
14+
Return the **maximum** length of an **increasing path** that contains `coordinates[k]`.
15+
16+
**Example 1:**
17+
18+
**Input:** coordinates = [[3,1],[2,2],[4,1],[0,0],[5,3]], k = 1
19+
20+
**Output:** 3
21+
22+
**Explanation:**
23+
24+
`(0, 0)`, `(2, 2)`, `(5, 3)` is the longest increasing path that contains `(2, 2)`.
25+
26+
**Example 2:**
27+
28+
**Input:** coordinates = [[2,1],[7,0],[5,6]], k = 2
29+
30+
**Output:** 2
31+
32+
**Explanation:**
33+
34+
`(2, 1)`, `(5, 6)` is the longest increasing path that contains `(5, 6)`.
35+
36+
**Constraints:**
37+
38+
* <code>1 <= n == coordinates.length <= 10<sup>5</sup></code>
39+
* `coordinates[i].length == 2`
40+
* <code>0 <= coordinates[i][0], coordinates[i][1] <= 10<sup>9</sup></code>
41+
* All elements in `coordinates` are **distinct**.
42+
* `0 <= k <= n - 1`

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.