Homework 2

[JinJinQuant]

Difficulty	Category	Title
Easy	Array	Kids With the Greatest Number of Candies
Easy	Array	Remove One Element to Make the Array Strictly Increasing
Easy	Array	Array Partition
Easy	Array	How Many Numbers Are Smaller Than the Current Number
Easy	Array	Matrix Diagonal Sum
Medium	Array	Gas Station
Easy	Array	Count Hills and Valleys in an Array
Easy	Array	Teemo Attacking
Easy	Array	Longest Harmonious Subsequence
Easy	Array	Maximize Sum Of Array After K Negations
Easy	Linked List	Merge Two Sorted Lists
Easy	Linked List	Reverse Linked List
Easy	Linked List	Linked List Cycle

[JinJinQuant]

1431. Kids With the Greatest Number of Candies

1. Straightforward way

   class Solution {
   public:
   vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
       int n = candies.size();
       int g = 0;
   
       vector<bool> answer(n, false);
   
       for(int i = 0; i < n; ++i){
           if(candies[i] >= g){
               g = candies[i];
           }
       }
   
       for(int i = 0; i < n; ++i){
           if(candies[i] + extraCandies >= g){
               answer[i] = true;
           }
       }
   
       return answer;
   }
   };

[JinJinQuant]

1909. Remove One Element to Make the Array Strictly Increasing

1. Backward Checking (Sliding Window with i-2,i-1,i) consider three adjacent elements, remove = replace with the i-1 th value, backward

   class Solution {
   public:
   bool canBeIncreasing(vector<int>& nums) {
       int n = nums.size();
       int cnt = 0;
       for(int i=1; i<n; i++){
           if(nums[i-1]>=nums[i]){
               if(cnt > 0){
                   return false;
               }
               cnt++;
               // [i-2] >= [i] -> can't make a strictly increasing even if we remove [i-1] (replace [i] with [i-1])
               if(i>1 && nums[i-2] >= nums[i]){ 
                   nums[i] = nums[i-1];
               }
           }
       }
       return true;
   }
   };

[JinJinQuant]

561. Array Partition

1. Straightforwad

   class Solution {
   public:
   int arrayPairSum(vector<int>& nums) {
       sort(nums.begin(), nums.end());
   
       int sum = 0;
       for(int i=0; i<nums.size(); i += 2){
           sum += nums[i];
       }
       return sum;
   }
   };

[JinJinQuant]

1365. How Many Numbers Are Smaller Than the Current Number

1. Hashmap - matching (O(n)) + Sorting (O(nlogn))

   class Solution {
   public:
   vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
       unordered_map<int,int> h;
       vector<int> temp = nums; // dummy variable for sorting (to preserve the order of original)
       sort(temp.begin(), temp.end());
   
       for(int i=nums.size()-1; i>=0; i--){
           h[temp[i]] = i; // # of values smaller than the number (not equal)
       }
   
       for(int i=0; i<nums.size(); i++){
           nums[i] = h[nums[i]];
       }
   
       return nums;
   }
   };

[JinJinQuant]

1572. Matrix Diagonal Sum

1. Straightforwad

   class Solution {
   public:
   int diagonalSum(vector<vector<int>>& mat) {
       int rows = mat.size();
       int columns = mat[0].size();
       if (rows != columns) return 0;
   
       int sum = 0;
       for(int i=0; i<rows; i++){
           sum += mat[i][i] + mat[i][columns-1-i];
       }
       // If the matrix odd size, subtract the middle element (added twice)
       if (rows%2 == 1) sum -= mat[rows/2][columns/2];
       return sum;
   }
   };

[JinJinQuant]

134. Gas Station

1. The existence of solution

   class Solution {
   public:
   int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
       int n = gas.size();
       int tank = 0, total_gas = 0, total_cost = 0, start = 0;
   
       for(int i=0; i<n; i++){
           total_gas += gas[i];
           total_cost += cost[i];
           tank += gas[i] - cost[i];
   
           // go though the path without emptying
           // if the tank ran out in the middle, initialize the starting point with the next
           if(tank < 0){
               start = i + 1;
               tank = 0;
           }
           // don't need to worry that it can go through the entire path without running out of the tank 
           // since the existence of a solution is guaranteed, even though start with the last
       }
       if (total_gas < total_cost){
           return -1;
       }
       return start;
   }
   };

[JinJinQuant]

2210. Count Hills and Valleys in an Array

1. Capturing changes

   class Solution {
   public:
   int countHillValley(vector<int>& nums) {
       int n = nums.size();
       if (n < 3) return 0;
   
       int ans = 0;
       int left = nums[0];  // Initialize the left value to the first element.
   
       for (int i = 1; i < n - 1; i++) {
           if (nums[i] != nums[i + 1]) {  // Only consider changes in value.
               if ((left < nums[i] && nums[i] > nums[i + 1]) ||
                   (left > nums[i] && nums[i] < nums[i + 1])) {
                   ans++;
               }
               left = nums[i];
           }
       }
   
       return ans;
   }
   };

[JinJinQuant]

495. Teemo Attacking

1. Straightforward

   class Solution {
   public:
   int findPoisonedDuration(vector<int>& timeSeries, int duration) {
       int n = timeSeries.size();
       int ans = 0;
   
       for(int i=0; i<n-1; i++){
           ans += min(duration, timeSeries[i+1]-timeSeries[i]);
       }
       ans += duration;
       return ans;
   }
   };

[JinJinQuant]

594. Longest Harmonious Subsequence

1. Hash map (O(n))

   class Solution {
   public:
   int findLHS(vector<int>& nums) {
       unordered_map<int,int> freq;
       int ans = 0;
   
       for(int i=0; i<nums.size(); ++i){
           freq[nums[i]]++;
       }
   
       for(auto tuple : freq){
           if(freq.find(tuple.first+1) != freq.end()) {
               // if there is a number with the difference of 1, combine the lengths of corresonding numbers
                   ans = max(ans, tuple.second + freq[tuple.first+1]);
           }
       }
       return ans;        
   }
   };

[JinJinQuant]

1005. Maximize Sum Of Array After K Negations

1. Sort, Convert negatives, and Process remainings

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());

        // convert all negative values to postive ones as much
        for(int i=0; i<nums.size() && k>0 && nums[i]<0; i++){
            nums[i] = -nums[i];
            k--;
        }

        int sum = 0;
        for(int v: nums){
            sum += v;
        }

        // if still remains k
        if(k%2 == 1){
            int min = nums[0];
            for(int i=0; i<nums.size(); i++){
                if(nums[i] < min) min = nums[i];
            }
            sum -= 2*min;
        }

        return sum;
    }
};

[JinJinQuant]

1. Recursion

   /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode() : val(0), next(nullptr) {}
   *     ListNode(int x) : val(x), next(nullptr) {}
   *     ListNode(int x, ListNode *next) : val(x), next(next) {}
   * };
   */
   class Solution {
   public:
   ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
       if(list1 == NULL){
           return list2;
       }else if(list2 == NULL){
           return list1;
       }
   
       if(list1->val <= list2->val){
           list1->next = mergeTwoLists(list1->next, list2);
           return list1;
       }else{
           list2->next = mergeTwoLists(list1, list2->next);
           return list2;
       }
   }
   };

[JinJinQuant]

206. Reverse Linked List

1. Change the direction of each element

   /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode() : val(0), next(nullptr) {}
   *     ListNode(int x) : val(x), next(nullptr) {}
   *     ListNode(int x, ListNode *next) : val(x), next(next) {}
   * };
   */
   class Solution {
   public:
   ListNode* reverseList(ListNode* head) {
       ListNode* left = nullptr;
   
       // reverse the direction of the list from right to left
       while(head != nullptr){
           ListNode* right = head->next;
           head->next = left;
           // move our view to the next element to the right
           left = head; 
           head = right;
       }
   
       return left;
   }
   };

[JinJinQuant]

141. Linked List Cycle

1. Floyd's Cycle Finding Algorithm (O(n)) (!= Floyd-Warshall algorithm)

   class Solution {
   public:
   bool hasCycle(ListNode *head) {
       ListNode* fast = head;
       ListNode* slow = head;
   
       while(fast != nullptr && fast->next){
           slow = slow->next;
           fast = fast->next->next;
           if(slow == fast) return true;
       }
       return false;
   }
   };

2. Leverage hash map and check memory address O(n^2) time complexity and O(n) space complexity --> Floyd's algorithm is much better than this

   class Solution {
   public:
   bool hasCycle(ListNode *head) {
       std::unordered_set<ListNode*> addresses;
       while(head != nullptr){
           if(addresses.find(head) != addresses.end()){
               return true;
           }
           addresses.insert(head);
           head = head->next;
       }
       return false;
   }
   };