Largest Values From Labels

We have a set of items: the i-th item has value values[i] and label labels[i].
Then, we choose a subset S of these items, such that:
|S| <= num_wanted
For every label L, the number of items in S with label L is <= use_limit.

Return the largest possible sum of the subset S.

Example 1:

Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth item.

Example 2:

Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
Output: 12
Explanation: The subset chosen is the first, second, and third item.

Example 3:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
Output: 16
Explanation: The subset chosen is the first and fourth item.

Example 4:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
Output: 24
Explanation: The subset chosen is the first, second, and fourth item.

Note:

1. 1 <= values.length == labels.length <= 20000
2. 0 <= values[i], labels[i] <= 20000
3. 1 <= num_wanted, use_limit <= values.length

Solution: 

We need to sort the values and their labels in non-ascending order and then just choose the top num_wanted based on use_limit.

For use_limit we use a count array.

Code:

Duplicate Zeros

Given a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written.

Do the above modifications to the input array in place, do not return anything from your function.

Example 1:

Input: [1,0,2,3,0,4,5,0]
Output: null
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: [1,2,3]
Output: null
Explanation: After calling your function, the input array is modified to: [1,2,3]

-----------------------------------------------------------------------------------------------------------------

Solution:

The only catch here is to not use any extra space. The insertion should be in place. We will make use if insert property of vectors in C++ STL. Code below - 

Code:

Adding Two Negabinary Numbers

Given two numbers arr1 and arr2 in base -2, return the result of adding them together.

Each number is given in array format:  as an array of 0s and 1s, from most significant bit to least significant bit.  For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3.  A number arr in array format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.

Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

Example 1:

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]
Output: [1,0,0,0,0]
Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

Solution: 

Negabinary numbers are numbers with base -2.
There are three basic rules for negabinary addition (base 10 equivalent in brackets)

• 1 (1) + 1(1) = 110 (2)
• 1 (1) + 1(1) + 1(1) = 111 (3)
• 11 (-1) + 1 (1) = 0 (0)

Let's see a step by step addition of numbers in the example above - 11111 + 101
Step 1:
Adding LSB, 1+1 = 110, we have carry = 11

Step 2:
Adding next LSB + carry

Step 3:
Adding next LSB + carry








Step 4:
Adding next LSB + carry

Step 5:
Adding next LSB + carry

Step 6:
Finally the carry is 11 (-1) + 1 (1) which is equal to 0.

Code :

Flip Columns For Maximum Number of Equal Rows

Given a matrix consisting of 0s and 1s, we may choose any number of columns in the
matrix and flip every cell in that column. Flipping a cell changes the value of that cell
from 0 to 1 or from 1 to 0.
Return the maximum number of rows that have all values equal after some
number of flips.

Example 1:
Input: [[0,1],[1,1]]
Output: 1 Explanation: After flipping no values, 1 row has all
values equal.
Example 2:
Input: [[0,1],[1,0]]
Output: 2 Explanation: After flipping values in the first column, both rows
have equal values.

Example 3:
Input: [[0,0,0],[0,0,1],[1,1,0]]
Output: 2 Explanation: After flipping values in the first two columns, the last two rows
have equal values.
Note:
1 <= matrix.length <= 300
1 <= matrix[i].length <= 300
All matrix[i].length's are equal
matrix[i][j] is 0 or 1.

Solution:

Understanding the problem-

We need to flip columns such that all values in a row are equal. i.e. all 0s or all 1s
Any Row can have all values equal after some number of flips.
eg:
[0,0,1,0,0,0,1,0] can be [0,0,0,0,0,0,0,0] after flipping 3rd and 7th columns
or
[0,0,1,0,0,0,1,0] can be [1,1,1,1,1,1,1,1] after flipping all columns except 3rd and 7th.
So, in this question if we find the rows that are equal, i.e. row[i]==row[j] where i!=j,
0<=i<=rowsize, 0<=j<=rowsize,
the maximum number of equal rows will give us maximum number of rows that have all
values equal after some flips.

When are rows equal?

Suppose, we have 3 rows r1 = [0,1,0], r2 = [0,1,0] and r3 = [1,0,1]
As we can see, r1 = r2, since all elements in r1 and r2 are same.
What if I say, r1 = r3 in this case?
We can consider r1 = r3 here, since an element can have either 0 or 1 only as its value.
In the above example if we flip all elements of r3, it will be the same as r1.

So flipping the elements in 2nd column in all the rows will result in 3 rows, each having all
their elements equal
[0,0,0], [0,0,0], [1,1,1]

The answer here will be 3.


C++ solution -

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:

Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]





Solution :

The idea is to use DFS. If in a path from root to a leaf the sum is found, the path

is entered into a result vector. If not, we backtrack and look for other paths.



Code :



Do comment and share!

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Solution :
The list can be traveled once to get the count of nodes and place a pointer at the last node.
In the next step, the  list is traveled again from head, and each node having value greater than x is placed at the end of the list.

Code :


Please comment to suggest a better method.

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Solution :
Delete intermediate nodes that are same as the previous node. This works because the list is already sorted.

Code :

Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution :
The only thing to keep in my mind is that you cannot sell a stock before buying it.
We need to find max(Aj - Ai) where i
Code:

Permutations

Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].


Solution :
This is done recursively by making permutations resulting from swapping of two elements. The below diagram can make it clear.

We start with k=0 and swap the element at ith index with element at kth index.

At the first level for k = 0, we swap num[k] with num[i] where i varies from k to number of elements in the array. We do this at all levels where value of k increases till it is equal to the number of elements in the array.

Here is the program for it :

Please comment to add something.

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution:

This is solved using BFS. One way to print in levels is to keep 

2 queues.Current queue and a nextlevel queue. nextlevel queue 

has left and right children of the node popped from current 

queue.Once the current queue is empty we swap current queue 

with nextlevel queue.Another solution is to use only 1 queue and

keep track of level using variables. nodesInCurrentLevel & 

nodesInNextLevel.

Here is the source code.  

Do comment if you would like to add something to it.

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Solution :

We first find the digit starting from unit's place that is less than the preceding digit. In an Array A start with i = n-2. compare A[n-2] with A[n-1] and keep decrementing i till we find A[i]
For eg: in 1,3,2 we get i=0;
In another example 1,2,4,3,1,1 we get i =1. Hence the value 0 to i-1 need not be disturbed. We now need to find the next permutation of number starting from i.
We now need to find the next digit which is the least digit greater than A[i].
For that we move from the end of array and stop at k=3 (A[k]=3). We now swap A[i] and A[k]. So the array now is 1,3,4,2,1,1. Now we reverse the array starting from i+1. We now get 1,3,1,1,2,4 which is the next permutation.

Code: 

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Solution : 

This can be done by in place dynamic programming. The idea is to replace matrix[i][j] values with the minimum value that can be achieved (among two paths) to reach matrix[i][j].
We can reach matrix[i][j] through one of 
matrix[i-1][j] or
matrix[i][j-1]
We record the minimum of these two at matrix[i][j].

Code:
class Solution {
public:
    int minPathSum(vector > &grid) {
    int i,j;
     for(i=0;i
        for(j=0;j
        {
           if(!(i==0 && j==0))
            {
                if(i==0 && j>0)
                  grid[i][j] += grid[i][j-1];
              else  if(i> && j==0)
                 grid[i][j]  += grid[i-1][j];
               else
                 grid[i][j] += min(grid[i][j-1], grid[i-1][j]); 
             }
         }
         return grid[i][j];
}
};

Binary Tree PreOrder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Solution : 


CODE:
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector preorderTraversal(TreeNode *root) {
      
       vector result;
       stack s;
       if(root!=NULL)
       s.push(root);
       while(!s.empty()){
           TreeNode *curr = s.top();
           result.push_back(curr->val);
           s.pop();
           if(curr->right)
           s.push(curr->right);
           if(curr->left)
           s.push(curr->left);
       }
       return result;
    }
};

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?

Solution : 

Came across a beautiful solution in the official LeetCode's Discuss section.

Unfortunately no explanation was offered, hence will try to explain it here.

As in the case of the Single Number question, we need to manipulate the bits of the numbers in the array.

For eg : A = [ 2, 3, 3, 3]

We count the number of 1s for each bit position. Then find mod 3 of each of them. The bit positions having mod 3  equal to one are the bits that are set due to the number occurring once.

Writing the Binary Representation of the numbers.

                                                                  0 0 1 0

                                                                  0 0 1 1

                                                                  0 0 1 1

                                                                  0 0 1 1

                                                            ----------------

We count the number of 1s for each bit ->  0 0 4 3

Taking modulo 3 we get                             0 0 1 0

and that's our answer. -> 2

Here's the code : 

The code basically has 2 variables  one & two. 

one is used to  mark bits that have mod 3 = 1.

two is used to mark bits that have mod 3 = 2.

Hope that helped!

Single Number

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

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

Solution : 

Rule of thumb :  XORing a number with itself results in 0. 

eg: A = [2, 3, 3, 1, 1]

if we XOR the numbers we will be left with the number that only occurred once.

0010 ^ 0011 ^ 0011 ^ 0001 ^ 0001  = 0010 = 2.

Code : 

class Solution {
public:
    int singleNumber(int A[], int n) {
       int c = A[0] ;
       for(int i=1;i
           c=c^A[i];
       }
       return c;
    }

};

Hope that helped!

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Solution : 

Remove Nth Node From End of List

Given a linked list, remove the n^th node from the end of list and return its head.
For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Solution:

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {

       ListNode  *fast , *slow;
       fast=slow=head;
       for(int i=0; inext;
       if (fast==NULL) return head->next;
       else{
           while(fast->next!=NULL){
               fast=fast->next;
               slow=slow->next;
           }
           slow->next=slow->next->next;
       }
       return head;
    }
};

Not much to explain here.

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

This is the simple solution.
  
class Solution {
public:
    string longestCommonPrefix(vector &strs) {
 
         if(strs.size() == 0) return "";

        int num = strs.size();
        int len = strs[0].size();

        for(int j = 0; j            for(int i = 1; i                 if(strs[i][j]!=strs[i-1][j]){
                    return strs[0].substr(0,j);
                }
            }
        }
        return strs[0];    
    }
};

We have a string vector containing different strings. We start off with first letter of string (j=0).
 The other loop starts at i=1 pointing to the string at index 1 in the vector.
The outer loop is for iterating through particular j for all the strings.
In the first iteration of the inner loop i=1, j=0;
strs[1][0] refers to first character of the string at index 1.
strs[0][0] refers to the first character of the string at index 0.
Both of them are compared. If found unequal we return the substring strs[0].substr(0,0) which basically is null here.
In the second iteration of the inner loop i=2, j=0;
strs[2][0] (first character of the string at index 2) is compared with strs[1][0] (first character of string at index 1). Similarly we iterate through all the strings (i) comparing their first characters with the first character of the previous string (i-1).
Then the outer loop is incremented (we compare all strings for their second characters) and proceed so on.
In the worst case the complexity will be O(n².

Integer to Roman

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

Solution:
We take two arrays containing the special cases. Since the number will not be greater than 3999, we need to know the Roman representations of up to he number 1000.
M = 1000
D = 500
C = 100
L = 50
X = 10
V = 5
I = 1

Here's the code. I got it from the comments on the Leetcode's problem page. Concise and precise.

class Solution {
public:
    string intToRoman(int num) {
        string result;
        int newnum;
        int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string symbols[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        for(int i =0; i<13;i++)
        {
            newnum = num/values[i];
             num = num-newnum*values[i];
            while(newnum--)
            {
                result.append(symbols[i]);
            }
      
        }
        return result;
    }
};

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

This is a classic problem involving Catalan numbers.
Catalan numbers is calculated using 

Catalann = (1/n+1)2nCn

There are many counting problems in combinatorics whose solution is given by the Catalan numbers.

• C_n is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's . For example, the following are the Dyck words of length 6:

        XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

• Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, C_n counts the number of expressions containing n pairs of parentheses which are correctly matched:

         ((()))     ()(())     ()()()     (())()     (()())

 

In our case for n =3, we get 5 combinations as can be calculated.

 

We solve this problem using recursion. The basic idea is we keep 2 stocks of parentheses. Open and  Close. 

The combinations are made by picking parentheses from these stocks. When both these stocks are empty, we end up with one particular combination. We store it in our string vector and the recursion lets us find other combinations. Here's the code for it : 

  

class Solution {
public:
    vector generateParenthesis(int n) {

      vector ans;
      if (n>0) brackets(ans, "", n, 0);
      return ans;  

    }

    void brackets(vector & ans, string s, int openStock,  int closeStock) {
    if (openStock==0 && closeStock==0) ans.push_back(s);
 
   if(openStock>0) brackets(ans, s+"(", openStock-1, closeStock+1);
   if(closeStock>0) brackets(ans, s+")", openStock, closeStock-1);
}
};  

To understand, try dry run for n =2. It will help you understand better.