DEV Community: shubhsheth

Leetcode Merge Intervals - Solution & Video Explaination

shubhsheth — Wed, 05 Jan 2022 18:56:45 +0000

Solution

vector<vector<int>> merge(vector<vector<int>>& intervals) {

    // Edge Cases
    if (intervals.size() <= 1) {
        return intervals;
    }

    // Sorting
    sort(intervals.begin(), intervals.end());

    // Merging
    vector<vector<int>> result;
    result.push_back(intervals[0]);
    for (int i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] <= result.back()[1]) {
            if (intervals[i][1] > result.back()[1]) {
                result.back()[1] = intervals[i][1];
            }
        } else {
            result.push_back(intervals[i]);
        }
    }
    return result;
}

def merge(intervals):

    if len(intervals) <= 1:
        return intervals

    intervals.sort()

    merged = [intervals[0]]

    for interval in intervals[1:]:
        if interval[0] <= merged[-1][1]:
            if interval[1] > merged[-1][1]:
                merged[-1][1] = interval[1]
        else:
            merged.append(interval)

    return merged

Complexity

Runtime: O(nlogn)
Space: O(n)

Leetcode Reverse Integer - Solution and Video Explaination

shubhsheth — Wed, 06 Jan 2021 04:39:01 +0000

Solution

int reverse(int x) {
  int reversed = 0;
  int max = INT_MAX/10;

  while (x != 0) {

    if (abs(reversed) > max) {
      return 0;
    }

    reversed *= 10;
    reversed += (x % 10);
    x /= 10;
  }

  return reversed;
}

Complexity

Runtime: O(n)
Space: O(n)

Video + Solution: Leetcode Increasing Triplet Subsequence

shubhsheth — Mon, 21 Dec 2020 00:47:37 +0000

Solution

bool IncresingTripletSubsequence (vector<int> &nums) {
  int a = INT_MAX;
  int b = INT_MAX;

  for (int num : nums) {
    if (num <= a) {
      a = num;
    } else if (num <= b) {
      b = num;
    } else {
      return true;
    }
  }

  return false;        
}

Complexity

Runtime: O(n)
Space: O(1)

Leetcode Odd Even Linked List - Solution & Video Explaination

shubhsheth — Sat, 19 Dec 2020 21:01:55 +0000

Solution

/* 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) {}
}; */

ListNode* oddEvenList(ListNode* head) {
  if (head == nullptr) {
    return head;
  }

  ListNode* oddPointer = head;
  ListNode* evenHead = oddPointer->next;
  ListNode* evenPointer = evenHead;

  while(evenPointer != nullptr && evenPointer->next != nullptr) {
    oddPointer->next = evenPointer->next;
    oddPointer = oddPointer->next;
    evenPointer->next = oddPointer->next;
    evenPointer = evenPointer->next;
  }

  oddPointer->next = evenHead;
  return head;
}

Complexity

Runtime: O(n)
Space: O(1)

Leetcode Add Two Numbers - Solution & Video Explaination

shubhsheth — Thu, 10 Dec 2020 18:17:22 +0000

Solution

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  ListNode* result = new ListNode();
  ListNode* resultPointer = result;
  int carry = 0;
  while (l1 || l2) {
    int sum = carry;
    if (l1) {
      sum += l1->val;
      l1 = l1->next;
    }
    if (l2) {
      sum += l2->val;
      l2 = l2->next;
    }            
    carry = sum / 10;

    resultPointer->next = new ListNode(sum % 10);
    resultPointer = resultPointer->next;
  }

  if (carry) {
    resultPointer->next = new ListNode(carry);
  }

  return result->next;
}

Complexity

Runtime: O(n + m)
Space: O(1)

Leetcode Two Sum - Solution & Video Explaination

shubhsheth — Tue, 08 Dec 2020 00:29:00 +0000

Solving using the Brute Force method

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

  vector<int> target_indices;

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

      if(nums.at(i) + nums.at(j) == target) {
        target_indices.push_back(i);
        target_indices.push_back(j);
        break;
      }

    }
  }

  return target_indices;
}

Solving using Hashmaps

vector<int> TwoSum(vector<int>& nums, int target) {
  vector<int> target_indices;

  unordered_map<int, int> hash_table;
  for (int i = 0; i < nums.size(); i++) {
    int second_integer = target - nums.at(i);

    if (hash_table.find(second_integer) != hash_table.end()) {
      target_indices.push_back(i);
      target_indices.push_back(hash_table.find(second_integer)->second);
      break;
    } else {
      hash_table[nums.at(i)] = i;
    }
  }

  return target_indices;
}

Complexity

Runtime: O(n)
Space: O(1)