Posts tagged as “in place”

花花酱 LeetCode 1502. Can Make Arithmetic Progression From Sequence

By zxi on July 5, 2020

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

Example 1:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Example 2:

Input: arr = [1,2,4]
Output: false
Explanation: There is no way to reorder the elements to obtain an arithmetic progression.

Constraints:

2 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6

Solution 1: Sort and check.

Time complexity: O(nlog)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool canMakeArithmeticProgression(vector<int>& arr) {

sort(begin(arr), end(arr));

const int diff = arr[1] - arr[0];

for (int i = 2; i < arr.size(); ++i)

if (arr[i] - arr[i - 1] != diff) return false;

return true;

}

};

Java

// Author: Huahua

class Solution {

public boolean canMakeArithmeticProgression(int[] arr) {

Arrays.sort(arr);

int diff = arr[1] - arr[0];

for (int i = 2; i < arr.length; ++i)

if (arr[i] - arr[i - 1] != diff) return false;

return true;

}

python3

class Solution:

def canMakeArithmeticProgression(self, arr: List[int]) -> bool:

arr.sort()

diff = arr[1] - arr[0]

return all(i - j == diff for i, j in zip(arr[1:], arr[:-1]))

Solution 2: Rearrange the array

Find min / max / diff and put each element into its correct position by swapping elements in place.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool canMakeArithmeticProgression(vector<int>& arr) {

const int n = arr.size();

const auto [loit, hiit] = minmax_element(cbegin(arr), cend(arr));

const auto [lo, hi] = pair{*loit, *hiit};

if ((hi - lo) % (n - 1)) return false;

const int diff = (hi - lo) / (n - 1);

if (diff == 0) return true;

for (int i = 0; i < n; ++i) {

if ((arr[i] - lo) % diff) return false;

const int idx = (arr[i] - lo) / diff;

if (idx != i) swap(arr[i--], arr[idx]);

}

return true;

}

};

花花酱 LeetCode 48. Rotate Image

By zxi on October 2, 2019

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

Solution: 2 Passes

First pass: mirror around diagonal
Second pass: mirror around y axis

Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

void rotate(vector<vector<int>>& matrix) {

const int n = matrix.size();

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

swap(matrix[i][j], matrix[j][i]);

for (int i = 0; i < n; ++i)

reverse(begin(matrix[i]), end(matrix[i]));

}

};

花花酱 LeetCode 73. Set Matrix Zeroes

By zxi on February 9, 2019

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Solution 1

Use two arrays to track whether the i-th row / j-th column need to be zeroed.

Time complexity: O(mn)
Space complexity: O(m+n)

C++

class Solution {

public:

void setZeroes(vector<vector<int>>& matrix) {

const int m = matrix.size();

const int n = matrix[0].size();

vector<int> rows(m);

vector<int> cols(n);

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

rows[i] |= (matrix[i][j] == 0);

cols[j] |= (matrix[i][j] == 0);

}

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

if (rows[i] || cols[j]) matrix[i][j] = 0;

}

};

Solution 2

Use the first row / first col to indicate whether the i-th row / j-th column need be zeroed.

C++

class Solution {

public:

void setZeroes(vector<vector<int>>& matrix) {

const int m = matrix.size();

const int n = matrix[0].size();

bool col0 = false;

bool row0 = false;

for (int i = 0; i < m; ++i)

col0 |= (matrix[i][0] == 0);

for (int j = 0; j < n; ++j)

row0 |= (matrix[0][j] == 0);

for (int i = 1; i < m; ++i)

for (int j = 1; j < n; ++j)

if (matrix[i][j] == 0)

matrix[0][j] = matrix[i][0] = 0;

for (int i = 1; i < m; ++i)

for (int j = 1; j < n; ++j)

if (matrix[i][0] == 0 || matrix[0][j] == 0)

matrix[i][j] = 0;

if (row0)

for (int j = 0; j < n; ++j)

matrix[0][j] = 0;

if (col0)

for (int i = 0; i < m; ++i)

matrix[i][0] = 0;

}

};

花花酱 LeetCode 31. Next Permutation

By zxi on October 2, 2018

Problem

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Solution

Find the last acceding element x, swap with the smallest number y, y is after x that and y is greater than x.

Reverse the elements after x.

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua, 8 ms

class Solution {

public:

void nextPermutation(vector<int>& nums) {

int i = nums.size() - 2;

while (i >= 0 && nums[i + 1] <= nums[i]) --i;

if (i >= 0) {

int j = nums.size() - 1;

while (j >= 0 && nums[j] <= nums[i]) --j;

swap(nums[i], nums[j]);

}

reverse(begin(nums) + i + 1, end(nums));

}

};

Python3

# Author: Huahua, 48 ms

class Solution:

def nextPermutation(self, nums):

n = len(nums)

i = n - 2

while i >= 0 and nums[i] >= nums[i + 1]: i -= 1

if i >= 0:

j = n - 1

while j >= 0 and nums[j] <= nums[i]: j -= 1

nums[i], nums[j] = nums[j], nums[i]

nums[i + 1:] = nums[i+1:][::-1]

花花酱 LeetCode 27. Remove Element

By zxi on October 2, 2018

Problem

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4. Note that the order of those five elements can be arbitrary. It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Solution:

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int removeElement(vector<int>& nums, int val) {

int len = 0;

for (int num : nums)

if (num != val) nums[len++] = num;

return len;

}

};

Python3

class Solution:

def removeElement(self, nums, val):

l = 0

for num in nums:

if num != val:

nums[l], l = num, l + 1

return l

Posts tagged as “in place”

花花酱 LeetCode 1502. Can Make Arithmetic Progression From Sequence

Solution 1: Sort and check.

C++

Java

python3

Solution 2: Rearrange the array

C++

花花酱 LeetCode 48. Rotate Image

Solution: 2 Passes

C++

花花酱 LeetCode 73. Set Matrix Zeroes

Solution 1

C++

Solution 2

C++

花花酱 LeetCode 31. Next Permutation

Problem

Solution

C++

Python3

花花酱 LeetCode 27. Remove Element

Problem

Solution:

C++

Python3

Related Problems