-
Notifications
You must be signed in to change notification settings - Fork 0
/
squares_of_a_sorted_array.php
78 lines (66 loc) · 2.34 KB
/
squares_of_a_sorted_array.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
<?php
/**
* Squares of a Sorted Array
* @link https://leetcode.com/problems/squares-of-a-sorted-array
*
* Approach:
* There are 3 cases:
* 1. Only negative integers - just start pushing from the end, because highest negative int will be smallest after squaring
* 2. Only positive integers - just start pushing from the start, because array is sorted
* 3. Mix of negative and positive integers - find first positive integer's index using Binary Search,
* then start comparing last negative integer with first positive integer and push smaller one,
* because again last (highest) negative integer is smallest when squaring, so we are just comparing two smallest elements
*
* Time Complexity - O(log n + n) = O(n)
* Space Complexity - O(n)
*/
class Solution {
/**
* @param Integer[] $nums
* @return Integer[]
*/
public function sortedSquares($nums)
{
$start = 0;
$end = count($nums) - 1;
$sortedArray = [];
// Only negative integers
if ($nums[$end] < 0) {
for ($i = $end; $i >= 0; $i--) {
$sortedArray[] = pow($nums[$i], 2);
}
return $sortedArray;
}
// Only positive integers
if ($nums[$start] >= 0) {
for ($i = 0; $i <= $end; $i++) {
$sortedArray[] = pow($nums[$i], 2);
}
return $sortedArray;
}
// mix of negative and positive integers
$positiveStart = null;
while ($start <= $end) {
$mid = floor(($start + $end) / 2);
if ($nums[$mid] >= 0) {
$positiveStart = $mid;
$end = $mid - 1;
} else {
$start = $mid + 1;
}
}
$negativeStart = $positiveStart - 1;
while ($negativeStart >= 0 || $positiveStart < count($nums)) {
$negative = isset($nums[$negativeStart]) ? pow($nums[$negativeStart], 2) : null;
$positive = isset($nums[$positiveStart]) ? pow($nums[$positiveStart], 2) : null;
if (is_null($negative) || isset($positive) && $positive < $negative) {
$sortedArray[] = $positive;
$positiveStart++;
} else {
$sortedArray[] = $negative;
$negativeStart--;
}
}
return $sortedArray;
}
}