Posts

Rotate Array

Image
      Leetcode - 189 Rotate Array Problem:  https://leetcode.com/problems/rotate-array/ The given problem expects the given array to be rotated to the right by k steps.  For example, given [1, 2, 3, 4, 5, 6] and k = 3, we need to perform the following: and hence we get the array, [4, 5, 6, 1, 2, 3] We can generalize the problem as following: Given an array of n-elements, perform m-rotations by magnitudes r[0], r[1], ...., r[m-1] given as array r, either by left or right given by array d[0], d[1], d[2], ...., d[m-1]. If d[i] = 0, then rotate left or rotate right otherwise. We try solving this version of the problem. Finally we reduce the generalized problem into the original problem. Solution 1: Bruteforce -  O(mn) time, O(1
Post a Comment
Read more

STL Cheatsheet

 STL CHEATSHEET Link: Click here to get the detailed cheat sheet for C++ STL Library.
Post a Comment
Read more

MEDIAN FROM DATA STREAM

Image
 Leetcode - 295 Find Median From Data Stream Problem:  https://leetcode.com/problems/find-median-from-data-stream/ For a given stream of integers we need to return the median. Median is the middle value in a sorted integer list with odd number of elements and if the list has even number of elements then median is mean of  two middle values. Solution 1: Brute-force - O(nlogn), O(1) time, O(1) space [TLE] In this method we follow the most trivial method to find the median. We sort the container which stores the input from the stream. From the sorted container find the middle value(s) to find the median. The container can a vector as we can sort it easily, insert at the end in constant time and elements are indexed to find the middle value(s).           vector<int> arr; MedianFinder() { } void addNum(int num)
Post a Comment
Read more

Contains Duplicates

 Leetcode - 217/219/220 Contains Duplicate - I/II/III 1. Contains Duplicate - I https://leetcode.com/problems/contains-duplicate/ For example given an array [1,2,3,4,1] return true as 1 is repeated , return false all the elements in the array are unique.  Solution 1: Brute-Force method - O(n 2 ) time, O(1) space [TLE] While iterating the array check if the element  is repeated by comparing it with the rest of elements, if the values compared are equal return true. If the whole the array is traversed that means no element is repeated ,hence return false.                bool bruteForce(vector<int>& nums) {               for(int i = 0; i < nums.size(); ++i) {                   for(int j = i + 1; j < nums.size(); ++
Post a Comment
Read more