leetcode

commit 141176754da437857bc4f537c6d66b9b1d5a5c07
parent a527ca5155d1ae689854af214e3a623580c9a05c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 22 Jan 2023 13:19:05 +0100

Algorithm I: Day 2

Diffstat:
M
Problems/0189.cpp
 | 
14
++++++++++++--
M
Problems/0977.cpp
 | 
15
+++++++++++++++

2 files changed, 27 insertions(+), 2 deletions(-)
diff --git a/Problems/0189.cpp b/Problems/0189.cpp
@@ -1,12 +1,22 @@
+// O(n) memory solution
 class Solution {
 public:
   void rotate(vector<int> &nums, int k) {
     k %= nums.size();
     vector<int> t(k);
     for (int i = 0; i < k; i++) t[i] = nums[nums.size() - k + i];
-
     for (int i = nums.size() - k - 1; i >= 0; i--) nums[i + k] = nums[i];
-
     for (int i = 0; i < k; i++) nums[i] = t[i];
   }
 };
+
+// O(1) memory solution
+class Solution {
+public:
+  void rotate(vector<int> &nums, int k) {
+    k %= nums.size();
+    reverse(nums.begin(), nums.end());
+    reverse(nums.begin(), nums.begin() + k);
+    reverse(nums.begin() + k, nums.end());
+  }
+};
diff --git a/Problems/0977.cpp b/Problems/0977.cpp
@@ -1,3 +1,4 @@
+// Intuitive solution
 class Solution {
 public:
   vector<int> sortedSquares(vector<int> &nums) {
@@ -18,3 +19,17 @@ public:
     return res;
   }
 };
+
+// Intuitive solution, better execution
+// avoids recomputation of squares
+// avoids reversal of the array
+class Solution {
+public:
+    vector<int> sortedSquares(vector<int>& nums) {
+        int n = nums.size(), i=0, j =nums.size()-1;
+        vector<int> res(n);
+        for_each(nums.begin(), nums.end(), [](int &a) { a*=a; });
+        while(i<=j) res[--n] = nums[i]>nums[j] ? nums[i++] : nums[j--];
+        return res;
+    }
+};