🗓️Day 01 – Arrays
Topics: Array fundamentals
Problem solved:
#704 - Binary Search
#27 - Remove Element
#977 - Squares of a sorted Array

📚Concept Review – What is an array?

Array i s a data structure that stores a collection of elements of the same type in contiguous memory locations. It means we can access an item randomly in O(1) time. However, inserting or deleting elements takes high price. Because we should shifting elements, which takes O(n) time. Besides, the index of array starts from 0 instead of 1.
Highlight

• contiguous memory locations
• access randomly in O(1) time
• index starts from 0

---

🧩Problem solution – 704. BinarySearch

link

💡Problem description

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

1 <= nums.length <= 104
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.

🧭Thought Process

As the array is ascending, so we can use binary search rather than sequential travesal to decrease runtime complexity. Array in order – think about binary search
How to do?
Given two variables (left and right) to mark the first index and the last index. Then we can calculate the middle index(mid). Pick the middle num by mid. By comparing, we can know if the target is in the left sid or the right side, so we can choose whether left or right needs to be turned into mid. Repeat above steps until we find the target.

💻Code Implementation

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
};

⏱️Complexity Analysis

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

🧩Problem solution – 27. Remove Element

link

💡Problem description

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.

Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,,]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

🧭Thought Process

The first thing we should notice is in-place algorithm. It means that we should not use any other space. So that makes me think of swaping. What if we move all the elements that equal to the val at the end of the array by swaping.
How to do?
we can use two pointers, traverse the array from the beginning and the end towards each other. First, we move the left one until we met the val. Then, move th right unitl its value not equal to the val. Now, swap the elements at these two positions. Repeat the steps until the left meet the right.

💻Code Implementation

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int p1 = 0, p2 = 0;
        int i = 0, len = nums.size();
        int cnt = 0;
        p2 = len - 1;
        while (p1 <= p2) {
            if(nums[p1]==val){
                nums[p1] = nums[p2];
                nums[p2] = val;
                cnt++;
                p2--;
            }else{
                p1++;
            }
        }
        return len-cnt;
    }
};

⏱️Complexity Analysis

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

🧩Problem solution – 977. Squares of a Sorted Array

link

💡Problem description

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

🧭Thought Process

Imaging a coordinate system, the horizental axis is the index, and the vertical axis represents the squares of the elements. This char has two posibilities. It could be a V-shaped line chart ot it could be a straight line. For most of the problems like this, we just need to travese this chart from the begining and the end towards each other.
Compare, pick the bigger one, move. Repeat the steps unitl we traverse all the elements. Then we can get a new non-increasing array. At last, reverse the array.

💻Code Implementation

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 0);
        
        int i = 0, j = n - 1;
        int pos = n - 1;
        while(i<=j){
            if(nums[i]*nums[i]>nums[j]*nums[j]){
                ans[pos] = nums[i]*nums[i];
                i++;
                pos--;
            }else{
                ans[pos] = nums[j]*nums[j];
                j--;
                pos--;
            }
        }
        return ans;
    }
};

⏱️Complexity Analysis

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