Tag Archives: leetcode

Few leetcode solutions

Few leetcode solutions

Implement Queue using Stacks

Implement the following operations of a queue using stacks.

  • push(x) — Push element x to the back of queue.
  • pop() — Removes the element from in front of queue.
  • peek() — Get the front element.
  • empty() — Return whether the queue is empty.

Notes:

  • You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

class Queue {
private:
stack<int> s1,s2 ;

public:
// Push element x to the back of queue.
void push(int x) {
while(!s1.empty())
{

int top=s1.top();
s1.pop();
s2.push(top);
}
s1.push(x);
while(!s2.empty())
{

int top=s2.top();
s2.pop();
s1.push(top);
}
}

// Removes the element from in front of queue.
void pop(void) {
if(!s1.empty())
s1.pop();

}

// Get the front element.
int peek(void) {
if(!s1.empty())
return s1.top();
else
return 0;
}

// Return whether the queue is empty.
bool empty(void) {
if(s1.empty())
return true;
else
return false;
}
};

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

int majorityElement(vector&lt;int&gt;&amp; nums) {
unordered_map&lt;int,int&gt; hsh;
for(int i=0 ; i &lt; nums.size();i++)
{
if(hsh.find(nums[i]) ==hsh.end())
{
hsh[nums[i]]=1;
if(nums.size() ==1) return nums[i];
}
else
{
int count =hsh[nums[i]];
if((count +1) &gt; (nums.size()/2))
return nums[i];
else
hsh[nums[i]]=++count;
}
}
}

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

int singleNumber(vector&lt;int&gt;&amp; nums) {
int result = 0;
int n = nums.size();

int x, sum;
int size=sizeof(int)*16;// for 64 bit
// Iterate through every bit
for (int i = 0; i &lt; size; i++)
{
// Find sum of set bits at ith position in all
// elements
sum = 0;
//way to check bits
x = (1 &lt;&lt; i);
for (int j=0; j&lt; n; j++ )
{
if (nums[j] &amp; x)
sum++;
}

// The bits with sum not multiple of 3, are the
// bits of element with single occurrence.
if (sum % 3)
result |= x;
}

return result;
}

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

int searchInsertUtil(vector&lt;int&gt;&amp; nums, int target, int start , int end) {
int mid =(end+start)/2 ;
if(target &lt; nums[mid])
{
if(mid != start )
return searchInsertUtil(nums,target,0,mid-1);
return mid;
}
else if(target &gt; nums[mid])
{
if(mid !=end)
return searchInsertUtil(nums,target,mid+1,end);
else return mid+1;
}
else
return mid;
}
int searchInsert(vector&lt;int&gt;&amp; nums, int target) {
return searchInsertUtil(nums, target,0 , nums.size()-1);
}

Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

bool containsDuplicate(vector&lt;int&gt;&amp; nums) {
unordered_map&lt;int,int&gt; hsh;
for(int i=0 ; i &lt; nums.size();i++)
{
if(hsh.find(nums[i]) == hsh.end())
{
hsh.insert(make_pair(nums[i],nums[i]));
}
else
return true;
}
return false;
}

Excel Sheet Column Number

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -&gt; 1
    B -&gt; 2
    C -&gt; 3
    ...
    Z -&gt; 26
    AA -&gt; 27
    AB -&gt; 28

int titleToNumber(string s) {
//if(s==NULL) return 0;
int length=s.length();
int nBit=0,sum=0;
for(int i=length-1;i&gt;=0;i--)
{
sum+=(pow(26,nBit)*(s[i]-'A'+1));
nBit++;
}
return sum;
}

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

int hammingWeight(uint32_t n) {
int count =0 ;
while(n!=0)
{
n=n&amp;(n-1);
count ++;
}
return count;
}

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

For this problem, we can consider the time when S enter the loop for the 1st time, which we assume k step from the head. At this time, the F is already in k step ahead in the loop. When will they meet next time?
Still solve the function: t mod n = (k + 2t) mod n
Finally, when t = (n-k), S and F will meet, this is k steps before the start of the loop.

ListNode *detectCycle(ListNode *head) {

if(head == NULL || head-&gt;next==NULL ) return NULL;
ListNode* slow =head, *fast=head;

slow=head-&gt;next;
fast=head-&gt;next-&gt;next;
if(head !=NULL &amp;&amp; head-&gt;next !=NULL)
{
while( fast &amp;&amp; fast-&gt;next )
{
if(slow == fast)
{
fast=head;
while(slow-&gt;val != fast-&gt;val)
{
slow=slow-&gt;next;
fast=fast-&gt;next;
}
return slow;
}
slow=slow-&gt;next;
fast=fast-&gt;next-&gt;next;

}
}
return NULL;
}

Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Use multimap to store the index where the value is zero in matrix and then set for each index the row and column to 0.

void setZeroes(vector&lt;vector&lt;int&gt;&gt;&amp; matrix) {
int col=matrix[0].size();
int row=matrix.size();
multimap&lt;int,int&gt; hsh ;
for(int i=0 ; i &lt; row;i++)
{
for(int j=0 ; j &lt; col;j++)
{
if(matrix[i][j]==0)
{
hsh.insert(make_pair(i,j));
//break;
}
}
}
multimap&lt;int,int&gt;::iterator itr=hsh.begin();
while(itr != hsh.end())
{
for(int i=0 ; i &lt; col;i++)
{
matrix[(*itr).first][i]=0;
}
for(int i=0 ; i &lt; row;i++)
{
matrix[i][(*itr).second]=0;
}
itr++;
}

}

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

<strong>[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
</strong>

Given target = 3, return true.

Start from top right.If smaller , then go left  and if larger go down else if equal return true.

bool searchMatrix(vector&lt;vector&lt;int&gt;&gt;&amp; matrix, int target) {
int col = matrix[0].size()-1;
int row=0;
while(col &gt;=0 &amp;&amp; row &lt; matrix.size())
{
if(target &lt; matrix[row][col])
col--;
else if(target &gt; matrix[row][col])
row++;
else
return true;
}
return false;
}