Homework 1

[JinJinQuant]

Homework 1: Leetcode - Array

Difficulty	Topic	Problem Title	Frequency
Medium	Array	Find the Duplicate Number	1
Medium	Array	Merge Intervals	2
Medium	Array	Product of Array Except Self	2
Easy	Array	Replace Elements with Greatest Element on Right Side	2
Medium	Array	Non-overlapping Intervals	2
Easy	Array	Time Needed to Buy Tickets	2
Easy	Array	Can Place Flowers	2
Easy	Array	Distance Between Bus Stops	2
Hard	Array	Candy	3
Easy	Array	Transpose Matrix	3
Easy	Array	Monotonic Array	3
Medium	Array	Find the Winner of an Array Game	3

[JinJinQuant]

287. Find Duplicated Number

1. Brutal-force Method

   
   #include <vector>
   using namespace std;

class Solution { public: int findDuplicate(vector& nums) { int temp; for (int i = 0; i < nums.size(); i++) { temp = nums[i]; for (int j = i + 1; j < nums.size(); j++) { if (temp == nums[j]) { return temp; } } } return -1; // Return -1 or throw an exception if no duplicate is found } };

2. 

[JinJinQuant]

56. Merge Intervals

1. Sorting (Introspective sort - Quick + Heap) + Comaprison - TC: O(nlogn)

   
   class Solution {
   public:
   vector<vector<int>> merge(vector<vector<int>>& intervals) {
       int n = intervals.size();
   
       // First, sort the entire array by comparing the begin first and the end second
       // By doing this, we can ensure do not omit any overlaps in the following
       sort(intervals.begin(), intervals.end());
   
       vector<vector<int>> answer;
       for(auto interval : intervals){
           // check whether the interval should be added as a new or should be merged
           if(answer.empty() || answer.back()[1] < interval[0]){
               answer.push_back(interval);
           }
           else{
               // replace the end of interval with a bigger value
               answer.back()[1] = max(answer.back()[1], interval[1]);
           }
       }
       return answer;
   }
   };

[JinJinQuant]

238. Product of Array Except Self

Don't use the division operator

1. Prefix and Suffix product

   class Solution {
   public:
   vector<int> productExceptSelf(vector<int>& nums) {
       int n = nums.size();
   
       // declare vectors of the size of n and initialized with 1
       std::vector<int> prefix(n, 1);
       std::vector<int> suffix(n, 1);
   
       // ans[i] = prod of elements before * prod of ele after each index in the array
       for (int i = 1; i < n; ++i) {
           prefix[i] = prefix[i - 1] * nums[i - 1];
       }
   
       for (int i = n - 2; i >= 0; --i) {
           suffix[i] = suffix[i + 1] * nums[i + 1];
       }
   
       std::vector<int> answer(n);
       for (int i = 0; i < n; ++i) {
           answer[i] = prefix[i] * suffix[i];
       }
   
       return answer;
   }
   };

[JinJinQuant]

1299. Replace Elements with Greatest Element on Right Side

1. Straightforward

   class Solution {
   public:
   vector<int> replaceElements(vector<int>& arr) {
       int n = arr.size();
       int greatest = -1;
       vector<int> answer(n);
   
       for(int i = n-1; i >= 0; --i){
           answer[i] = greatest;
           if(arr[i] > greatest){
               greatest = arr[i];
           }
       }
       return answer;
   }
   };

[JinJinQuant]

435. Non-overlapping Intervals

1. find an adequate order

   class Solution {
   public:
   // sorting with the end value
   static bool compare(vector<int>& a, vector<int>& b){
       return a[1] < b[1];
   }
   
   int eraseOverlapIntervals(vector<vector<int>>& intervals) {
       int n = intervals.size();
       sort(intervals.begin(), intervals.end(), compare);
   
       int prev = 0;
       int count = 1;
   
       for(int i = 1; i < n; i++){
           if(intervals[i][0] >= intervals[prev][1]){
               prev = i;
               count++;
           }
       }
       return n - count;
   }
   };

[JinJinQuant]

2073. Time Needed to Buy Tickets

1. Simulation using Queue

   class Solution {
   public:
   int timeRequiredToBuy(vector<int>& tickets, int k) {
       int n = tickets.size();
       int answer = 0; // required time
       queue<pair<int, int>> q;
   
       // Initialize queue
       for (int i = 0; i < n; ++i) {
           q.push({i, tickets[i]});
       }
   
       while (!q.empty()) {
           auto [idx, ticket_count] = q.front();
   
           // Buy a ticket
           q.pop();
           ticket_count--;
           answer++;
   
           if (ticket_count == 0) { // If there are no tickets left to buy
               if (idx == k) {
                   return answer;
               }
           } else {
               // Push him back into the queue if he still has tickets left to buy
               q.push({idx, ticket_count});
           }
       }
       return answer;
   }
   };

[JinJinQuant]

605. Can Place Flowers

1. Hard-coding

   class Solution {
   public:
   bool canPlaceFlowers(vector<int>& flowerbed, int n) {
       int count = 0;
       int size = flowerbed.size();
   
       for (int i = 0; i < size; ++i) {
           if (flowerbed[i] == 0) {
               bool emptyLeft = (i == 0) || (flowerbed[i - 1] == 0);
               bool emptyRight = (i == size - 1) || (flowerbed[i + 1] == 0);
               if (emptyLeft && emptyRight) {
                   flowerbed[i] = 1; // Plant a flower here
                   count++;
                   if (count >= n) {
                       return true;
                   }
               }
           }
       }
       return count >= n;
   }
   };

[JinJinQuant]

1184. Distance Between Bus Stops

1. Implement modular operation

   class Solution {
   public:
   int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {
       int n = distance.size();
   
       // If start and destination are the same, the distance is zero
       if (start == destination) return 0;
   
       // Ensure start is less than destination for simplicity
       if (start > destination) {
           swap(start, destination);
       }
   
       int clockwise_distance = 0;
       int counter_clockwise_distance = 0;
   
       // Calculate clockwise distance
       for (int i = start; i != destination; i = (i + 1) % n) {
           clockwise_distance += distance[i];
       }
   
       // Calculate counter-clockwise distance
       for (int i = start; i != destination; i = (i - 1 + n) % n) {
           counter_clockwise_distance += distance[(i - 1 + n) % n];
       }
   
       return min(clockwise_distance, counter_clockwise_distance);
   }
   };

[JinJinQuant]

135. Candy

1. Inquire how to approach similar problems (local optimum)

   class Solution {
   public:
   int candy(vector<int>& ratings) {
       int n = ratings.size();
       int candy = n, i=1;
       while(i<n){
           if(ratings[i] == ratings[i-1]){
               i++;
               continue;
           }
   
           //For increasing slope
           int peak = 0;
           while(ratings[i] > ratings [i-1]){
               peak++;
               candy += peak;
               i++;
               if(i == n) return candy;
           }
   
           //For decreasing slope
           int valley = 0;
           while(i<n && ratings[i] < ratings[i-1]){
               valley++;
               candy += valley;
               i++;
           }
           candy -= min(peak, valley); //Keep only the higher peak
       }
       return candy;
   }
   };

[JinJinQuant]

867. Transpose Matrix

1. Straightforward

   class Solution {
   public:
   vector<vector<int>> transpose(vector<vector<int>>& matrix) {
       int n = matrix.size(); // # of rows
       int m = matrix[0].size(); // # of columns
       vector<vector<int>> matrix_T(m, vector<int>(n, 0)); // Transposed: m x n
   
       for (int i = 0; i < m; ++i) {
           for (int j = 0; j < n; ++j) {
               matrix_T[i][j] = matrix[j][i]; // Swap the indices to transpose
           }
       }
       return matrix_T;
   }
   };

[JinJinQuant]

896. Monotonic Array

1. Straightforward

   class Solution {
   public:
   bool isMonotonic(vector<int>& nums) {
       int n = nums.size();
       int isIncrease = 1;
       int isDecrease = 1;
   
       for(int i = 0; i < n-1; ++i){
           if(nums[i] > nums[i+1]){
               isIncrease *= 0;
           }
           if(nums[i] < nums[i+1]){
               isDecrease *= 0;
           }
       }
       return (isIncrease || isDecrease);
   }
   };

[JinJinQuant]

1535. Find the Winner of an Array Game

1. Simulation

   class Solution {
   public:
   int getWinner(vector<int>& arr, int k) {
       // Find the maximum element in the array.
       int maxElement = *max_element(arr.begin(), arr.end()); 
   
       // If k is greater than or equal to the array size, the maximum element wins.
       if (k >= arr.size())
           return maxElement; 
   
       int current_winner = arr[0]; // Initialize the current winner with the first element of the array.
       int current_streak = 0; // Initialize the current streak to 0.
   
       for (int i = 1; i < arr.size(); i++) {
           // If the current winner is greater than the next element, then he will win the next game.
           if (current_winner > arr[i])
               current_streak++; 
   
           // the current winner lost the game.
           else {
               current_streak = 1; // Reset the streak since new element becomes the winner.
               current_winner = arr[i]; // Update the current winner.
           }
   
           // If the current streak reaches k or the current winner is the maximum element
           if (current_streak == k || current_winner == maxElement)
               return current_winner; 
       }
   
       return current_winner; // Dummy return
   }
   };