Skip to content

Commit a3289e9

Browse files
committed
Update all solutions' changes in 2025-05-15.
1 parent 5c22e98 commit a3289e9

4 files changed

Lines changed: 507 additions & 0 deletions

File tree

Lines changed: 248 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,248 @@
1+
# 334. Increasing Triplet Subsequence - LeetCode Python/Java/C++/JS/C#/Go/Ruby Solutions
2+
3+
Visit original link: [334. Increasing Triplet Subsequence - LeetCode Python/Java/C++/JS/C#/Go/Ruby Solutions](https://leetcode.blog/en/leetcode/334-increasing-triplet-subsequence) for a better experience!
4+
5+
LeetCode link: [334. Increasing Triplet Subsequence](https://leetcode.com/problems/increasing-triplet-subsequence), difficulty: **Medium**.
6+
7+
## LeetCode description of "334. Increasing Triplet Subsequence"
8+
9+
Given an integer array `nums`, return `true` if there exists a triple of indices `(i, j, k)` such that `i < j < k` and `nums[i] < nums[j] < nums[k]`. If no such indices exists, return `false`.
10+
11+
### [Example 1]
12+
13+
**Input**: `nums = [1,2,3,4,5]`
14+
15+
**Output**: `true`
16+
17+
**Explanation**: `Any triplet where i < j < k is valid.`
18+
19+
### [Example 2]
20+
21+
**Input**: `nums = [5,4,3,2,1]`
22+
23+
**Output**: `false`
24+
25+
**Explanation**: `No triplet exists.`
26+
27+
### [Example 3]
28+
29+
**Input**: `nums = [2,1,5,0,4,6]`
30+
31+
**Output**: `true`
32+
33+
**Explanation**:
34+
35+
<p>The triplet (3, 4, 5) is valid because nums[3] == 0 &lt; nums[4] == 4 &lt; nums[5] == 6.</p>
36+
37+
38+
### [Constraints]
39+
40+
- `1 <= nums.length <= 5 * 10^5`
41+
- `-2^31 <= nums[i] <= 2^31 - 1`
42+
43+
**Follow up**: Could you implement a solution that runs in `O(n)` time complexity and `O(1)` space complexity?
44+
45+
## Intuition
46+
47+
To find an increasing triplet subsequence, we can track the smallest and second-smallest elements seen so far. If we encounter an element larger than both, we've found our triplet.
48+
49+
## Pattern of "Greedy Algorithm"
50+
51+
The `Greedy Algorithm` is a strategy that makes the locally optimal choice at each step with the hope of leading to a "globally optimal" solution. In other words, "local optima" can result in "global optima."
52+
53+
## Step by Step Solutions
54+
55+
1. Initialize `first` as the first element and `second` as infinity.
56+
2. Iterate through the array starting from the second element:
57+
- If current element > `second`, triplet found → return `true`.
58+
- If current element > `first`, update `second` to current element.
59+
- Else, update `first` to current element (keeping it the smallest seen so far).
60+
3. If loop completes without finding a triplet, return `false`.
61+
62+
## Complexity
63+
64+
- Time complexity: `O(N)`.
65+
- Space complexity: `O(1)`.
66+
67+
## Python
68+
69+
```python
70+
class Solution:
71+
def increasingTriplet(self, nums: List[int]) -> bool:
72+
first = nums[0]
73+
second = float('inf')
74+
75+
for i in range(1, len(nums)):
76+
if nums[i] > second:
77+
return True
78+
79+
if nums[i] > first:
80+
second = nums[i]
81+
else:
82+
first = nums[i]
83+
84+
return False
85+
```
86+
87+
## Java
88+
89+
```java
90+
class Solution {
91+
public boolean increasingTriplet(int[] nums) {
92+
int first = nums[0];
93+
int second = Integer.MAX_VALUE;
94+
95+
for (int i = 1; i < nums.length; i++) {
96+
if (nums[i] > second) {
97+
return true;
98+
}
99+
100+
if (nums[i] > first) {
101+
second = nums[i];
102+
} else {
103+
first = nums[i];
104+
}
105+
}
106+
return false;
107+
}
108+
}
109+
```
110+
111+
## C++
112+
113+
```cpp
114+
class Solution {
115+
public:
116+
bool increasingTriplet(vector<int>& nums) {
117+
int first = nums[0];
118+
int second = INT_MAX;
119+
120+
for (int i = 1; i < nums.size(); i++) {
121+
if (nums[i] > second) {
122+
return true;
123+
}
124+
125+
if (nums[i] > first) {
126+
second = nums[i];
127+
} else {
128+
first = nums[i];
129+
}
130+
}
131+
132+
return false;
133+
}
134+
};
135+
```
136+
137+
## JavaScript
138+
139+
```javascript
140+
/**
141+
* @param {number[]} nums
142+
* @return {boolean}
143+
*/
144+
var increasingTriplet = function (nums) {
145+
let first = nums[0]
146+
let second = Infinity
147+
148+
for (let i = 1; i < nums.length; i++) {
149+
if (nums[i] > second) {
150+
return true
151+
}
152+
153+
if (nums[i] > first) {
154+
second = nums[i]
155+
} else {
156+
first = nums[i]
157+
}
158+
}
159+
160+
return false
161+
};
162+
```
163+
164+
## C#
165+
166+
```csharp
167+
public class Solution {
168+
public bool IncreasingTriplet(int[] nums) {
169+
int first = nums[0];
170+
int second = int.MaxValue;
171+
172+
for (int i = 1; i < nums.Length; i++) {
173+
if (nums[i] > second) {
174+
return true;
175+
}
176+
177+
if (nums[i] > first) {
178+
second = nums[i];
179+
} else {
180+
first = nums[i];
181+
}
182+
}
183+
184+
return false;
185+
}
186+
}
187+
```
188+
189+
## Go
190+
191+
```go
192+
func increasingTriplet(nums []int) bool {
193+
first := nums[0]
194+
second := math.MaxInt32
195+
196+
for _, num := range nums[1:] {
197+
if num > second {
198+
return true
199+
}
200+
201+
if num > first {
202+
second = num
203+
} else {
204+
first = num
205+
}
206+
}
207+
208+
return false
209+
}
210+
```
211+
212+
## Ruby
213+
214+
```ruby
215+
# @param {Integer[]} nums
216+
# @return {Boolean}
217+
def increasing_triplet(nums)
218+
first = nums[0]
219+
second = Float::INFINITY
220+
221+
nums[1..].each do |num|
222+
if num > second
223+
return true
224+
end
225+
226+
if num > first
227+
second = num
228+
else
229+
first = num
230+
end
231+
end
232+
233+
false
234+
end
235+
```
236+
237+
## Other languages
238+
239+
```java
240+
// Welcome to create a PR to complete the code of this language, thanks!
241+
```
242+
243+
Dear LeetCoders! For a better LeetCode problem-solving experience, please visit website [LeetCode.blog](https://leetcode.blog): Dare to claim the best practices of LeetCode solutions! Will save you a lot of time!
244+
245+
Original link: [334. Increasing Triplet Subsequence - LeetCode Python/Java/C++/JS/C#/Go/Ruby Solutions](https://leetcode.blog/en/leetcode/334-increasing-triplet-subsequence).
246+
247+
GitHub repository: [leetcode-python-java](https://github.com/leetcode-python-java/leetcode-python-java).
248+

en/1-1000/605-can-place-flowers.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,10 @@ Given an integer array `flowerbed` containing `0`'s and `1`'s, where `0` means e
3333

3434
Check each empty plot (`0`). If both adjacent plots are empty (or boundaries), plant a flower (set to `1`) and count. Return `true` if the final count ≥ `n`, otherwise `false`.
3535

36+
## Pattern of "Greedy Algorithm"
37+
38+
The `Greedy Algorithm` is a strategy that makes the locally optimal choice at each step with the hope of leading to a "globally optimal" solution. In other words, "local optima" can result in "global optima."
39+
3640
## Step by Step Solutions
3741

3842
1. Initialize counter `count = 0`.

0 commit comments

Comments
 (0)