Algo-DS interview prep in a glance. Leetcode questions & their answers compiled in one place.

leetcode-answers.md

1. Two Sum

Total Accepted: 372574
Total Submissions: 1273263
Difficulty: Easy
Contributors: Admin

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

UPDATE (2016/2/13): The return format had been changed to zero-based indices. Please read the above updated description carefully.

Approach #3 (One-pass Hash Table) [Accepted]

It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element's complement already exists in the table. If it exists, we have found a solution and return immediately.

---

2. Add Two Numbers

Total Accepted: 219342
Total Submissions: 843677
Difficulty: Medium
Contributors: Admin

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

---

3. Longest Substring Without Repeating Characters

Total Accepted: 223827
Total Submissions: 949264
Difficulty: Medium
Contributors: Admin

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

We use HashSet to store the characters in current window [i,j)[i, j)[i,j) (j=ij = ij=i initially). Then we slide the index jjj to the right. If it is not in the HashSet, we slide jjj further. Doing so until s[j] is already in the HashSet. At this point, we found the maximum size of substrings without duplicate characters start with index iii. If we do this for all iii, we get our answer.

---

4. Median of Two Sorted Arrays

Total Accepted: 133399
Total Submissions: 645867
Difficulty: Hard
Contributors: Admin

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3] nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2] nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution - for arrays of size m & n, median will be at (m+n)/2 from start of the combined array. Run i & j on each array such that .....

---

5. Longest Palindromic Substring

Total Accepted: 156595
Total Submissions: 643330
Difficulty: Medium
Contributors: Admin

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n−12n - 12n−1 such centers.

You might be asking why there are 2n−12n - 12n−1 but not nnn centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as ''abba'' ) and its center are between the two 'b'

s.

public String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

---

Serialize & deserialize binary tree

Serialize - preorder traversal . Mark nil children as nil. Root, left, right node order

def serialize (node)
    return "nil" if node.nil?
    string = ""
    string += node.val + ","
    string += serialize(node.left) + ","
    string += serialize(node.right) + ","
end

def deserialize (s)
    node.left = _deserialize(val_array,count++)
    node.right = _deserialize(val_array,count++)
end

def _deserialize(val_array,i)
   if val_array[i].nil?
       return
   else
        
            
end

450. Delete Node in a BST

Steps:

Recursively find the node that has the same value as the key, while setting the left/right nodes equal to the returned subtree Once the node is found, have to handle the below 4 cases node doesn't have left or right - return null node only has left subtree- return the left subtree node only has right subtree- return the right subtree node has both left and right - find the minimum value in the right subtree, set that value to the currently found node, then recursively delete the minimum value in the right subtree

def delete_node(node,val)
    if val > node.val
        delete_node(node.right,val)
    elseif val < node.val
        delete_node(node.left,val)
    else #current node need deletion
        if node.left.nil?
            return node.right
        elseif node.right.nil?
            return node.left
        else
            replacement = find_replacement(node.left)
            node.val = replacement.val
            delete_node(node,replacement.val)
        end
    end
 end
 
 def find_replacement(node,val)
    while !node.right.nil?
        node = node.right
    end
    return node
 end

Add Numbers (2)

Given 2 linked list of numbers , add them 7->0->4->3 + 3->8->5 = 7->1->2-> 8

def sum(l1, l2)
    c1 = l1.length
    c2 = l2.length
    count = [c1,c2].max
    out = LL.new(count)
    carry = _sum(l1,l2,count,out)
    if carry == 1
        #create new node & append before out
    end
    out
end

def _sum(l1,l2,count,out)
    return 0 if count == 0
    if c1 >= count
        out.val += l1.val
        l1 = l1.next
    end
    if c2 >= count
        out.val += l2.val
        l2 = l2.next
    end
    out.val += _sum(l1,l2,count--,out.next)
    if out.val > 10
        out.val %= 10
        return 1
    else
        return 0
    end
 end

---

451. Sort Characters By Frequency QuestionEditorial Solution My Submissions

Total Accepted: 8586 Total Submissions: 17129 Difficulty: Medium Contributors: stickypens Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input: "tree"

Output: "eert"

Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Build a map of characters to the number of times it occurs in the string Create an array where the index of the array represents how many times that character occurred in the String Iterate from the end of the array to the beginning, and at each index, append each character to the return string that number of times.

---

Poor Pig

1000 bucks, one has poision. One pig drinks the water & dies in 15 min. How many pigs needed to identify the bucket in 60 min

x * x-1 * x-2 * x-3 = 1000 .. x comes around 8

---

11. Container With Most Water

Add to List QuestionEditorial Solution My Submissions Total Accepted: 107167 Total Submissions: 297862 Difficulty: Medium Contributors: Admin Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Sol - start from both ends, i & j . Increment i if height[i] < height[j] .. reason j is already greater than i & hence the area calculation is (j-1) * height[j] .. we start at boundaries where (j-i) is max .. then we move the value which is smaller so that height increases but j-i is decreasing .. do this till j converges with i

---

Problem - find kth minimum number in an array

Sol 1 - k size priority queue
Sol 2 - Quick select algorithm - quick select works like quick sort .. select a random pivot & get all values less than pivot on left & more than pivot on the right. The pivot position might also shift in this process. If k < new pivot position, that means kth element is on the left. Pick that part & repeat till k == pivot position

def quick_select(array, start, end, pivot, k)
  while start < end
     while array[start] < array[pivot] and start < end
         start += 1
     end
     while array[end] >= array[pivot] and start < end
         end -= 1
     end 
     if end > start
       swap(array, start, end)
     end
     if start == pivot
         pivot = end
     end
     if end == pivot
         pivot = start
      end
  end
  if k == pivot
     return array[pivot]
   elseif k < pivot #go left
      return quick_select(array, start, pivot - 1, k)
   else
       return quick_select(array, pivot+1, end, k - pivot)
   end
end

LeetCode – Range Addition (Java)

Assume you have an array of length n initialized with all 0's and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

Sol :-

def range_addition(array, triplets)
  output = []
  triplets.each do |triplet|
     [start, end, inc] = triplet
     output[start] += inc
     output[end + 1] -= inc 
  end
  sum = 0
  array.each_with_index do |val, i|
     sum += output[i]
     output[i] = sum
   end
end

Leetcode: Find the Celebrity
Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1people know him/her but he/she does not know any of them.
Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).
You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.
Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.

Sol :- i=0, j = n-1 .. if knows(i,j) == 0 => j cant be celebrity as i does not know him (a celebrity is known by everyone) .. so j = j-1 .. if knows(i,j) == 1 => j could be celebrity as i knows him, lets check with the next person .. so i = i + 1 .. run the loop till i crosses j . final j is the celebrity position.

38. Product of Array Except Self QuestionEditorial Solution My Submissions
    Total Accepted: 77160
    Total Submissions: 164404
    Difficulty: Medium
    Contributors: Admin
    Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Sol :- first loop from left to right, at position i - accumulate product of values before i & overwrite array. So at position i - the value is product of all left values . 2nd loop, start from the end & move back. At pos i - we now need to multiply values which are at position > i * val[i] . Start accumulating from the right. ... its kind of hard explaining :(

Question - find majority element - count > length/2 - in an array

Solution -

public class Solution {
    public int majorityElement(int[] num) {

        int major=num[0], count = 1;
        for(int i=1; i<num.length;i++){
            if(count==0){
                count++;
                major=num[i];
            }else if(major==num[i]){
                count++;
            }else count--;
            
        }
        return major;
    }
}

Modified version - find majority number such that - occurence > length/3 .. there could be 2 such elements.
Solution - keep two counters & majority element holder. Increase count of either of the element when found. If the given number is neither of the two then only decrease both counts by 1. Remember - this avoid decreasing the count of one of the element when the other is found.

LeetCode – Maximum Subarray (Java)

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Sol - dynamic programming - keep accumulating sum from the left. At any index - if sum till prev number is < current number that means the sum till prev number is going to bring down the sum at current number. So discard sum. Sum at current index is the number at the index itself. If the sum > max_sum => max_sum = sum .

Similar problem - LeetCode – Maximum Product Subarray (Java)

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

Sol - maintain min & max at every index. As min value is needed if the current value is < 0. max[i] = max(max[i-1]*a[i-1],a[i]) if a[i] > 0 . if max_val < max[i] => max_val = max[i] . If a[i] < 0 => max[i] = max(min[i-1] * a[i-1], a[i]) . Recalculate min[i] at i as well.

209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

public int minSubArrayLen(int s, int[] a) {
  if (a == null || a.length == 0)
    return 0;
  
  int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
  
  while (j < a.length) {
    sum += a[j++];
    
    while (sum >= s) {
      min = Math.min(min, j - i);
      sum -= a[i++];
    }
  }
  
  return min == Integer.MAX_VALUE ? 0 : min;
}

167. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Sol - since array is sorted - two pointer approach starting from beginning & end can be used. if sum of the 2 numbers > given sum => end pointer -- else if sum < given sum => start pointer ++ else we have the answer.

153. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Sol - Classic binary search problem.

Looking at subarray with index [start,end]. We can find out that if the first member is less than the last member, there's no rotation in the array. So we could directly return the first element in this subarray.

If the first element is larger than the last one, then we compute the element in the middle, and compare it with the first element. If value of the element in the middle is larger than the first element, we know the rotation is at the second half of this array. Else, it is in the first half in the array.

Follow up - if duplicates are allowed

class Solution {
public:
    int findMin(vector<int> &num) {
        int lo = 0;
        int hi = num.size() - 1;
        int mid = 0;
        
        while(lo < hi) {
            mid = lo + (hi - lo) / 2;
            
            if (num[mid] > num[hi]) {
                lo = mid + 1;
            }
            else if (num[mid] < num[hi]) {
                hi = mid;
            }
            else { // when num[mid] and num[hi] are same
                hi--;
            }
        }
        return num[lo];
    }
};

When num[mid] == num[hi], we couldn't sure the position of minimum in mid's left or right, so just let upper bound reduce one.

121. Best Time to Buy and Sell Stock

Say you have an array for which the ith 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.

Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

def max_profit(prices)
    max_profit = 0
    buy = nil
    prices.each_with_index do |val,i|
        if prices[i+1] and val < prices[i+1]
            buy = val
        elsif prices[i+1] and val > prices[i+1] 
            next if buy.nil?
            profit = val - buy
            max_profit = profit if profit > max_profit
            buy = nil
        else #next price is not there
            if buy
                profit = val - buy
                max_profit = profit if profit > max_profit
            end
        end
    end
    return max_profit
end