Homework 4

[JinJinQuant]

Difficulty	Category	Problem	Rating
Easy	Two Pointers	Sort Array By Parity	3
Easy	Two Pointers	Squares of a Sorted Array	3
Medium	Two Pointers	Remove Duplicates from Sorted Array II	3
Medium	String	Longest Substring Without Repeating Characters	1
Medium	String	Minimum Add to Make Parentheses Valid	2
Easy	String	Valid Palindrome	2
Easy	String	First Unique Character in a String	2
Medium	String	Group Anagrams	3
Easy	Stack	Valid Parentheses	1
Hard	Stack	Largest Rectangle in Histogram	3
Medium	Stack	Asteroid Collision	3
Medium	Stack	Daily Temperatures	3
Easy	Stack	Final Prices With a Special Discount in a Shop	3

[JinJinQuant]

905. Sort Array By Parity

1. Brute-force

   class Solution:
   def sortArrayByParity(self, nums: List[int]) -> List[int]:
   
       lst_odd = [i for i in nums if i%2 == 1]
       lst_even = [i for i in nums if i%2 == 0]
   
       return lst_even + lst_odd

[JinJinQuant]

977. Squares of a Sorted Array

1. Brute-force (O(nlogn))

   
   class Solution:
   def sortedSquares(self, nums: List[int]) -> List[int]:
       lst = [i**2 for i in nums]
       lst.sort()
       return lst

2. 
```python
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        res = [0] * len(nums)
        left = 0
        right = len(nums) - 1

        for i in range(len(nums) - 1, -1, -1):
            if abs(nums[left]) > abs(nums[right]):
                res[i] = nums[left] ** 2
                left += 1
            else:
                res[i] = nums[right] ** 2
                right -= 1

        return res

[JinJinQuant]

80. Remove Duplicates from Sorted Array II

class Solution {
    public int removeDuplicates(int[] nums) {

        int index = 1;
        int occurance = 1;

        for(int i=1; i < nums.length; i++){
            if (nums[i] == nums[i-1]){
                occurance++;
            }else{
                occurance = 1;
            }

            if (occurance <= 2){
                nums[index] = nums[i];
                index++;
            }
        }  

        return index;

    }
}

[JinJinQuant]

3. Longest Substring Without Repeating Characters

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = max_length = 0
        char_set = set()

        for right in range(len(s)):
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1

            char_set.add(s[right])
            max_length = max(max_length, right - left + 1)

        return max_length