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.
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;
}
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.
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 .....
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 - 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
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
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
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.
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
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
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
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.