Posts tagged as “array”

花花酱 LeetCode 80. Remove Duplicates from Sorted Array II

By zxi on September 30, 2019

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice 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.

Example 1:

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

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

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

Example 2:

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

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Solution:

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

C++

// Author: Huahua

class Solution {

public:

int removeDuplicates(vector<int>& nums) {

const int n = nums.size();

if (n <= 2) return n;

int index = 1;

int len = 1;

int last = nums[0];

while (index < n) {

int count = 1;

while (index < n && nums[index] == last) {

++count;

++index;

}

if (count >= 2) nums[len++] = last;

if (index < n) {

last = nums[index++];

nums[len++] = last;

}

return len;

}

};

花花酱 LeetCode 1200. Minimum Absolute Difference

By zxi on September 22, 2019

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

a, b are from arr
a < b
b - a equals to the minimum absolute difference of any two elements in arr

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]

Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

Constraints:

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

Solution: Sorting

The min abs difference could only happen between consecutive numbers in sorted form.

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> minimumAbsDifference(vector<int>& arr) {

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

vector<vector<int>> ans;

int best = INT_MAX;

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

int d = abs(arr[i] - arr[i - 1]);

if (d < best) {

ans.clear();

best = d;

}

if (d == best) ans.push_back({arr[i - 1], arr[i]});

}

return ans;

}

};

花花酱 LeetCode 1184. Distance Between Bus Stops

By zxi on September 7, 2019

A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given start and destination stops.

Example 1:

Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.

Example 2:

Input: distance = [1,2,3,4], start = 0, destination = 2
Output: 3
Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.

Example 3:

Input: distance = [1,2,3,4], start = 0, destination = 3
Output: 4
Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.

Constraints:

1 <= n <= 10^4
distance.length == n
0 <= start, destination < n
0 <= distance[i] <= 10^4

Solution: Summation

compute the total sum
compute the sum from s to d, c
ans = min(c, sum – c)

Time complexity: O(d-s)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int distanceBetweenBusStops(vector<int>& ds, int s, int d) {

if (s > d) swap(s, d);

int sum = accumulate(begin(ds), end(ds), 0);

int d1 = accumulate(begin(ds) + s, begin(ds) + d, 0);

return min(d1, sum - d1);

}

};

花花酱 LeetCode 34. Find First and Last Position of Element in Sorted Array

By zxi on August 20, 2019

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Solution: Binary Search

Basically this problem asks you to implement lower_bound and upper_bound using binary search.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> searchRange(vector<int>& nums, int target) {

return {firstPos(nums, target), lastPos(nums, target)};

}

private:

int firstPos(const vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

int m = l + (r - l) / 2;

if (nums[m] >= target) {

r = m;

} else {

l = m + 1;

}

if (l == nums.size() || nums[l] != target) return -1;

return l;

}

int lastPos(const vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

int m = l + (r - l) / 2;

if (nums[m] > target) {

r = m;

} else {

l = m + 1;

}

// l points to the first element this is greater than target.

--l;

if (l < 0 || nums[l] != target) return -1;

return l;

}

};

花花酱 LeetCode 217. Contains Duplicate

By zxi on July 22, 2019

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Solution 1: HashTable

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

C++

// Author: Huahua, 48ms/16.5MB

class Solution {

public:

bool containsDuplicate(vector<int>& nums) {

unordered_set<int> s;

for (int num : nums)

if (!s.insert(num).second) return true;

return false;

}

};

Solution 2: Sorting

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

C++

// Author: Huahua, 28ms/11.4MB

class Solution {

public:

bool containsDuplicate(vector<int>& nums) {

sort(begin(nums), end(nums));

for (int i = 1; i < nums.size(); ++i)

if (nums[i] == nums[i - 1]) return true;

return false;

}

};

Posts tagged as “array”

花花酱 LeetCode 80. Remove Duplicates from Sorted Array II

Solution:

C++

Related Problems

花花酱 LeetCode 1200. Minimum Absolute Difference

Solution: Sorting

C++

花花酱 LeetCode 1184. Distance Between Bus Stops

C++

花花酱 LeetCode 34. Find First and Last Position of Element in Sorted Array

Solution: Binary Search

C++

花花酱 LeetCode 217. Contains Duplicate

Solution 1: HashTable

C++

Solution 2: Sorting

C++