Skip to content

Commit 5c599ec

Browse files
gazeldxgazeldx
committed
977-squares-of-a-sorted-array.md Added 7 languages' solution.
1 parent c32bea9 commit 5c599ec

2 files changed

Lines changed: 341 additions & 1 deletion

File tree

‎README.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,8 @@ You can skip the more difficult problems and do them later.
1414

1515
# Array
1616
- [704. Binary Search](solutions/1-1000/704-binary-search.md) was solved in _Python, Java, C++, JavaScript, C#, Go, Ruby_.
17-
- [27. Remove Element](solutions/1-1000/27-remove-element.md)
17+
- [27. Remove Element](solutions/1-1000/27-remove-element.md) was solved in _Python, Java, C++, JavaScript, C#, Go, Ruby_ and **2** solutions.
18+
- [977. Squares of a Sorted Array](solutions/1-1000/977-squares-of-a-sorted-array.md) was solved in _Python, Java, C++, JavaScript, C#, Go, Ruby_.
1819
- [503. Next Greater Element II](solutions/1-1000/503-next-greater-element-ii.md) was solved in _Python, Java, C++, JavaScript, C#, Go, Ruby_.
1920

2021
# Dynamic Programming

‎solutions/1-1000/977-squares-of-a-sorted-array.md‎

Lines changed: 339 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,339 @@
1+
# 977. Squares of a Sorted Array - LeetCode Solution
2+
LeetCode problem link: [977. Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array)
3+
4+
## LeetCode problem description
5+
Given an integer array `nums` sorted in **non-decreasing** order, return _an array of **the squares of each number** sorted in non-decreasing order._
6+
7+
### Example 1
8+
```ruby
9+
Input: nums = [-4,-1,0,3,10]
10+
Output: [0,1,9,16,100]
11+
Explanation: After squaring, the array becomes [16,1,0,9,100].
12+
After sorting, it becomes [0,1,9,16,100].
13+
```
14+
15+
### Example 2
16+
```ruby
17+
Input: nums = [-7,-3,2,3,11]
18+
Output: [4,9,9,49,121]
19+
```
20+
21+
### Constraints
22+
- `1 <= nums.length <= 10000`
23+
- `10000 <= nums[i] <= 10000`
24+
- `nums` is sorted in **non-decreasing** order.
25+
26+
**Follow up**: Squaring each element and sorting the new array is very trivial, could you find an `O(n)` solution using a different approach?
27+
28+
## Intuition behind the Solution
29+
### Solution 1: using `sort()`
30+
* Square each number in the array.
31+
* Sort the new array.
32+
33+
### Solution 2: not using `sort()` (important)
34+
* The smallest number in the array is located inside the array, and you need to traverse to find it.
35+
* But if you think in reverse and give priority to the certain ones, the program will become simple.
36+
* The largest number in the array is located at the two ends. So, deal with the largest number first.
37+
38+
## Complexity
39+
### Solution 1: using `sort()`
40+
* Time: `O(n * log n)`.
41+
* Space: `O(n)`.
42+
43+
### Solution 2: not using `sort()`
44+
* Time: `O(n)`.
45+
* Space: `O(n)`.
46+
47+
## Java
48+
### Solution 1: using `sort()`
49+
```java
50+
class Solution {
51+
public int[] sortedSquares(int[] nums) {
52+
for (var i = 0; i < nums.length; i++) {
53+
nums[i] *= nums[i];
54+
}
55+
56+
Arrays.sort(nums);
57+
58+
return nums;
59+
}
60+
}
61+
```
62+
63+
### Solution 2: not using `sort()`
64+
```java
65+
class Solution {
66+
public int[] sortedSquares(int[] nums) {
67+
var results = new int[nums.length];
68+
var left = 0;
69+
var right = nums.length - 1;
70+
var index = right;
71+
72+
while (left <= right) {
73+
if (Math.abs(nums[left]) <= nums[right]) {
74+
results[index] = nums[right] * nums[right];
75+
right -= 1;
76+
} else {
77+
results[index] = nums[left] * nums[left];
78+
left += 1;
79+
}
80+
81+
index -= 1;
82+
}
83+
84+
return results;
85+
}
86+
}
87+
```
88+
89+
## Python
90+
### Solution 1: using `sort()`
91+
```python
92+
class Solution:
93+
def sortedSquares(self, nums: List[int]) -> List[int]:
94+
results = [num ** 2 for num in nums]
95+
96+
results.sort()
97+
98+
return results
99+
```
100+
101+
### Solution 2: not using `sort()`
102+
```python
103+
class Solution:
104+
def sortedSquares(self, nums: List[int]) -> List[int]:
105+
results = [None] * len(nums)
106+
left = 0
107+
right = index = len(nums) - 1
108+
109+
while left <= right:
110+
if abs(nums[left]) <= nums[right]:
111+
results[index] = nums[right] ** 2
112+
right -= 1
113+
else:
114+
results[index] = nums[left] ** 2
115+
left += 1
116+
117+
index -= 1
118+
119+
return results
120+
```
121+
122+
## C++
123+
### Solution 1: using `sort()`
124+
```cpp
125+
class Solution {
126+
public:
127+
vector<int> sortedSquares(vector<int>& nums) {
128+
for (auto i = 0; i < nums.size(); i++) {
129+
nums[i] *= nums[i];
130+
}
131+
132+
sort(nums.begin(), nums.end());
133+
134+
return nums;
135+
}
136+
};
137+
```
138+
139+
### Solution 2: not using `sort()`
140+
```cpp
141+
class Solution {
142+
public:
143+
vector<int> sortedSquares(vector<int>& nums) {
144+
auto results = vector<int>(nums.size());
145+
auto left = 0;
146+
int right = nums.size() - 1; // Should not use 'auto' here because 'auto' will make this variable become `unsigned long` which has no `-1`.
147+
auto index = right;
148+
149+
while (left <= right) {
150+
if (abs(nums[left]) <= nums[right]) {
151+
results[index] = nums[right] * nums[right];
152+
right -= 1;
153+
} else {
154+
results[index] = nums[left] * nums[left];
155+
left += 1;
156+
}
157+
158+
index -= 1;
159+
}
160+
161+
return results;
162+
}
163+
};
164+
```
165+
166+
## JavaScript
167+
### Solution 1: using `sort()`
168+
```javascript
169+
var sortedSquares = function (nums) {
170+
return _.sortBy(
171+
nums.map((num) => num * num)
172+
)
173+
};
174+
```
175+
176+
### Solution 2: not using `sort()`
177+
```javascript
178+
var sortedSquares = function (nums) {
179+
const results = Array(nums.length).fill(0)
180+
let left = 0
181+
let right = nums.length - 1
182+
let index = right
183+
184+
while (left <= right) {
185+
if (Math.abs(nums[left]) <= nums[right]) {
186+
results[index] = nums[right] * nums[right]
187+
right -= 1
188+
} else {
189+
results[index] = nums[left] * nums[left]
190+
left += 1
191+
}
192+
193+
index -= 1
194+
}
195+
196+
return results
197+
};
198+
```
199+
200+
## C#
201+
### Solution 1: using `sort()`
202+
```c#
203+
public class Solution {
204+
public int[] SortedSquares(int[] nums) {
205+
for (int i = 0; i < nums.Length; i++) {
206+
nums[i] *= nums[i];
207+
}
208+
209+
Array.Sort(nums);
210+
211+
return nums;
212+
}
213+
}
214+
```
215+
216+
### Solution 2: not using `sort()`
217+
```c#
218+
public class Solution {
219+
public int[] SortedSquares(int[] nums) {
220+
var results = new int[nums.Length];
221+
int left = 0;
222+
int right = nums.Length - 1;
223+
int index = right;
224+
225+
while (left <= right)
226+
{
227+
if (Math.Abs(nums[left]) <= nums[right])
228+
{
229+
results[index] = nums[right] * nums[right];
230+
right -= 1;
231+
}
232+
else
233+
{
234+
results[index] = nums[left] * nums[left];
235+
left += 1;
236+
}
237+
238+
index -= 1;
239+
}
240+
241+
return results;
242+
}
243+
}
244+
```
245+
246+
## Go
247+
### Solution 1: using `sort()`
248+
```go
249+
func sortedSquares(nums []int) []int {
250+
for i, _ := range nums {
251+
nums[i] *= nums[i]
252+
}
253+
254+
sort.Sort(sort.IntSlice(nums))
255+
256+
return nums
257+
}
258+
```
259+
260+
### Solution 2: not using `sort()`
261+
```go
262+
func sortedSquares(nums []int) []int {
263+
results := make([]int, len(nums))
264+
left := 0
265+
right := len(nums) - 1
266+
index := right
267+
268+
for left <= right {
269+
if math.Abs(float64(nums[left])) <= float64(nums[right]) {
270+
results[index] = nums[right] * nums[right]
271+
right -= 1
272+
} else {
273+
results[index] = nums[left] * nums[left]
274+
left += 1
275+
}
276+
277+
index -= 1
278+
}
279+
280+
return results
281+
}
282+
```
283+
284+
## Ruby
285+
### Solution 1: using `sort()`
286+
```ruby
287+
def sorted_squares(nums)
288+
nums.map { |num| num ** 2 }.sort
289+
end
290+
```
291+
292+
### Solution 2: not using `sort()`
293+
```ruby
294+
def sorted_squares(nums)
295+
results = Array.new(nums.length)
296+
left = 0
297+
right = nums.size - 1
298+
index = right
299+
300+
while left <= right
301+
if nums[left].abs <= nums[right]
302+
results[index] = nums[right] * nums[right]
303+
right -= 1
304+
else
305+
results[index] = nums[left] * nums[left]
306+
left += 1
307+
end
308+
309+
index -= 1
310+
end
311+
312+
results
313+
end
314+
```
315+
316+
## C
317+
```c
318+
// Welcome to create a PR to complete the code of this language, thanks!
319+
```
320+
321+
## Kotlin
322+
```kotlin
323+
// Welcome to create a PR to complete the code of this language, thanks!
324+
```
325+
326+
## Swift
327+
```swift
328+
// Welcome to create a PR to complete the code of this language, thanks!
329+
```
330+
331+
## Rust
332+
```rust
333+
// Welcome to create a PR to complete the code of this language, thanks!
334+
```
335+
336+
## Other languages
337+
```
338+
// Welcome to create a PR to complete the code of this language, thanks!
339+
```

0 commit comments

Comments
 (0)