A summary of the problem statement, Java and Python code is posted.
Contains Duplicate Description
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.
Example 1:
Input: [1,2,3,1] Output: true
Example 2:
Input: [1,2,3,4] Output: false
Example 3:
Input: [1,1,1,3,3,4,3,2,4,2] Output: true
Solution Code
solution.java
// return true if there are dup items in array
// pre: nums[1,2,3,1]
// post: true
public boolean containsDuplicate(int[] nums) {
// corner case: if nums.length <= 1, return false
if (nums.length <= 1) return false;
Map<Integer, Boolean> map = new HashMap<>();
// single linear scan left -> right, build hashMap as we go
for (int num : nums) {
// if map.containsKey(nums[i]) == true, then dup found so return true
if (map.containsKey(num)) return true;
map.put(num, true);
}
// return false
return false;
}
solution.py
class Solution:
# return true if nums[] contains duplicate
# pre: nums[1,2,3,1]
# post: true
def containsDuplicate(self, nums: List[int]) -> bool:
# corner case: nums is empty or size 1, return false
if len(nums) <= 1:
return False;
# step1: single linear scan left -> right, build hashMap as we go
map = {}
for num in nums:
# step 2: if map.containsKey(nums[i]) == true, then dup found so return true
if num in map:
return True;
map[num] = True
return False;
First Unique Character in a String Description
Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.
Examples:
s = "leetcode" return 0.
s = "loveleetcode" return 2.
Note: You may assume the string contains only lowercase English letters. Solution Code
solution.java
// return index of first char that is unique
// pre: s="leetcode"
// post: 0
public int firstUniqChar(String s) {
// corner case: if s.length <=1, return 0
if (s.length() == 1) return 0;
Map<Integer, Integer> map = new HashMap<>();
// need to scan all the chars and keep count of occurrence
for (char c : s.toCharArray()) {
if (!map.containsKey((int) c)) {
map.put((int) c, 1);
}
else {
map.put((int) c, map.get((int) c) + 1); // increment count
}
}
// second pass: need to go through string again to return index
for (int i = 0; i < s.length(); i++) {
if (map.get((int) s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
solution.py
class Solution:
# return index of first unique char in array
# pre: s = "leetcode"
# post: 0
def firstUniqChar(self, s: str) -> int:
map = {}
# step1: single linear scan left -> right
for char in s:
if char in map:
map[char] = map[char] + 1
else:
map[char] = 1
# step 2: second pass, need to go through string again to return index
for i in range(0, len(s)):
if map[s[i]] == 1:
return i
return -1
Two Sum Description
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, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
Solution Code
solution.java
public int[] twoSum(int[] nums, int target) {
// clarification: guaranteed to have a pair sums up to target
int[] result = new int[2];
// logic: single linear scan left-right - nums[0...i...N-1]
Map<Integer, Integer> hashmap = new HashMap<>();
// test case: [2,7,1], target=3
for (int i = 0; i < nums.length; i++) {
// if nums[i] is in hashMap or hashMap.contains(target - nums[i]), then found it, need to return indeces so return [i, hashMap.get(nums[i])]
if (hashmap.containsKey(nums[i])) {
result[0] = hashmap.get(nums[i]);
result[1] = i;
break;
}
// else, put target-nums[i] and i as key-value as Entry(diff, index)
hashmap.put(target - nums[i], i);
}
return result;
}
solution.py
class Solution:
# return indeces of two items summing up to target
# pre: nums[2,7,11,15],target=9
# post: [0,1]
def twoSum(self, nums: List[int], target: int) -> List[int]:
results = []
map = {}
# step1: linear scan array left -> right, and build map
for i in range(0, len(nums)):
# step 2: check if (target - nums[i]) exists in hashmap, if so return two indices
complement = target - nums[i]
if complement in map:
# return indeces
results.append(map[complement])
results.append(i)
else:
# step 3: else, add (nums[i], i) to hashmap
map[nums[i]] = i
return results;
Reverse String Description
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Example 1:
Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"]
Example 2:
Input: ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]
Solution Code
solution.java
// reverse chars in array in-place
// pre: chars[dog]
// post: chars[god]
public void reverseString(char[] s) {
// input check: if empty, return s
if (s.length == 0) return;
// run front & end indeces toward the middle and swap
int front = 0;
int end = s.length - 1;
// test1: char[d,o,g], front=0, end=2
// test2: char[d,o], front=0, end=1
while (front < end) {
char tmp = s[front];
s[front] = s[end];
s[end] = tmp;
front++;
end--;
// test1: char[g,o,d], front=1, end=1
// test2: char[o,d], front=1, end=0
}
}
solution.py
class Solution:
# reverse chars in string in place
# pre: s="dog"
# post: s="god"
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
def swap(s: List[str], front: int, end: int):
tmp = s[front]
s[front] = s[end]
s[end] = tmp
# step1: run front & end indeces toward the middle
front = 0
end = len(s) - 1
# testcases: s="", s="a", s="ab", s="abc"
while front < end:
# step 2: swap array[front] and array[end]
swap(s, front, end)
# step 3: move indeces
front += 1
end -= 1
Move Zeroes Description
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12] Output: [1,3,12,0,0]
Note:
You must do this in-place without making a copy of the array. Minimize the total number of operations.
Solution Code
solution.java
// move zeros to the end while maintaining non-zero item's order
// pre: nums[0,1,0,3,12]
// post: nums[1,3,12,0,0]
public void moveZeroes(int[] nums) {
// corner case: if nums.length == 0, return it
if (nums.length == 0) return;
int nonZeroLast = 0;
int runnerIndex = 0;
// linear scan left -> right while runnerIndex < nums.length
while (runnerIndex < nums.length) {
// split array into two sections, non-zero and zero sections using two indeces
// if nums[runnerIndex] != 0, then swap(nums[nonZeroLast], nums[runnerIndex])
// test case: nums[0,1,0,3,12], nonZeroIndex=0, runner=0
// test case: nums[0,1,0,3,12], nonZeroIndex=0, runner=1
// test case: nums[1,0,0,3,12], nonZeroIndex=1, runner=2
// test case: nums[1,0,0,3,12], nonZeroIndex=1, runner=3
if (nums[runnerIndex] != 0) {
swap(nums, nonZeroLast, runnerIndex);
// advance nonZeroLast only when after swapped
nonZeroLast++;
}
// always advance runnerIndex++
// test case: nums[0,1,0,3,12], nonZeroIndex=0, runner=1
// test case: nums[1,0,0,3,12], nonZeroIndex=1, runner=2
// test case: nums[1,0,0,3,12], nonZeroIndex=1, runner=3
// test case: nums[1,3,0,0,12], nonZeroIndex=2, runner=4
runnerIndex++;
}
return;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
solution.py
class Solution:
# move all zeros toward the end, while maintaining non-zero item order
# pre: nums[0,1,0,3,12]
# post: nums[1,3,12,0,0]
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def swap(nums: List[int], i: int, j: int):
tmp = nums[i]
nums[i] = nums[j]
nums[j] = tmp
# step1: linear scan left -> right while runnerIndex < nums.length
nonZeroLastIndex = 0
runner = 0
# testcases: nums[], nums[1], nums[1,3], nums[1,3,0], nums[0], nums[0,3], nums[1,0,3]
while runner < len(nums):
# step 2: split array into two sections, non-zero and zero sections using two indeces
# step 3: if nums[runnerIndex] != 0, then swap(nums[nonZeroLast], nums[runnerIndex])
if nums[runner] != 0:
swap(nums, nonZeroLastIndex, runner)
nonZeroLastIndex += 1
runner += 1
Remove Element Description
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example 1:
Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,1,2,2,3,0,4,2], val = 2,
Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
Note that the order of those five elements can be arbitrary.
It doesn't matter what values are set beyond the returned length.
Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
Solution Code
solution.java
// "remove val from array" (move them to end) and return length of non-val-array
// pre: nums[3,2,2,3], val=3
// post: 2, nums[2,2,3,3]
public int removeElement(int[] nums, int val) {
// corner case: val might not exist
// single linear scan left -> right
int nonValLastIndex = 0;
int runner = 0;
// testcase1: nums[3,2,2,3], val=3, nonVal=0, runner=0
// testcase1: nums[3,2,2,3], val=3, nonVal=0, runner=1
// testcase1: nums[2,3,2,3], val=3, nonVal=1, runner=2
// testcase1: nums[2,2,3,3], val=3, nonVal=2, runner=3
// testcase2: nums[3,3], val=3, nonVal=0, runner=0
// testcase2: nums[3,3], val=3, nonVal=0, runner=1
// testcase3: nums[2,3], val=3, nonVal=0, runner=0
// testcase3: nums[2,3], val=3, nonVal=1, runner=1
while (runner < nums.length) {
// split array into two sections: non-val vs val
// if nums[runner] == val, then move on
// if nums[runner] != val, swap(nums[nonValLastIndex], nums[runner] )
if (nums[runner] != val) {
swap(nums, nonValLastIndex, runner);
nonValLastIndex++;
}
runner++;
}
// return nonValLastIndex
return nonValLastIndex;
}
private void swap(int[] nums, int index1, int index2) {
int tmp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = tmp;
}
solution.py
class Solution:
# return length of array section without value
# pre: nums[3,2,2,3], val=3
# post: 2 (nums[2,2,3,3])
def removeElement(self, nums: List[int], val: int) -> int:
def swap(nums: List[int], i: int, j: int):
tmp = nums[i]
nums[i] = nums[j]
nums[j] = tmp
# step1: linear scan left -> right while runnerIndex < nums.length
nonValLastIndex = 0
runner = 0
# testcase: nums[3,2,2,3], val=0
while runner < len(nums):
# step 2: split array into two sections, non-val and val sections using two indeces
# step 3: if nums[runnerIndex] != val, then swap(nums[nonValLastIndex], nums[runnerIndex])
if nums[runner] != val:
swap(nums, nonValLastIndex, runner)
nonValLastIndex += 1
runner += 1
return nonValLastIndex;
making...
Recommended Posts