Last updated on September 4th, 2023
Coming from a business background, shifting to the tech world has been quite a ride. When I first entered this new field, most of my energy and time was dedicated to learning new technologies, tools, languages, and frameworks. Consequently, I unintentionally neglected one important skill – algorithms.
Four years after the first day I stepped foot into the tech world, I’ve decided to address this gap by embarking on a 21-day Leetcode challenge. It’s a popular belief that forming a habit takes 21 days (I can’t be sure, but I’ve applied this concept to numerous activities), and I’m keen to develop the habit of consistently tackling algorithms.
This post is nothing but my day’s progress tracking. I’ll pick a random Leetcode challenge and try it myself. Happy coding!
The source code for these examples can be found on the GitHub repo
Note: This challenge is paused on day 15 and will be resumed later.
Day 15: Aug 09 2023 – Best Time to Buy and Sell Stock
Difficulty Level: Easy
It should pass below test cases:
private static Stream<Arguments> inputExpectedProfit() {
return Stream.of(
Arguments.of(new int[]{1}, 0),
Arguments.of(new int[]{5, 5, 5, 5, 5}, 0),
Arguments.of(new int[]{3, 2}, 0),
Arguments.of(new int[]{5, 4, 3, 2, 1}, 0),
Arguments.of(new int[]{7, 6, 4, 3, 1}, 0),
Arguments.of(new int[]{2, 1, 2, 1, 0, 1, 2}, 2),
Arguments.of(new int[]{2, 4, 1}, 2),
Arguments.of(new int[]{7, 1, 5, 3, 6, 4}, 5)
);
}
We can solve this challenge by a brute-force approach using nested loops, which can lead time complexity is O(n^2). However, let’s track the minimum price and maximum profit while looping the arrays as below:
public static int maxProfit(int[] prices) {
int maxProfit = 0;
int minPrice = prices[0];
for (int i = 1; i < prices.length; i++) {
int currentProfit = prices[i] - minPrice;
if (currentProfit > maxProfit) {
maxProfit = currentProfit;
}
if (prices[i] < minPrice) {
minPrice = prices[i];
}
}
return maxProfit;
}
The time complexity is now O(n), where n is the length of the input array.
Day 14: Aug 08 2023 – Valid Palindrome
Difficulty Level: Easy
It should pass below test cases:
@ParameterizedTest
@MethodSource("palindromeString")
@DisplayName("Should return true when the input is a palindrome str")
void testIsStringPalindromeWhenTrue(String input) {
assertTrue(isStringPalindrome(input));
}
@ParameterizedTest
@MethodSource("nonPalindromeString")
@DisplayName("Should return false when the input is not a palindrome str")
void testIsStringPalindromeWhenFalse(String input) {
assertFalse(isStringPalindrome(input));
}
private static Stream<Arguments> palindromeString() {
return Stream.of(
Arguments.of("A man, a plan, a canal, Panama!"),
Arguments.of("A man, a plan, a canal, Panama"),
Arguments.of("A man, a plan, a canal: Panama!"),
Arguments.of(" "),
Arguments.of("")
);
}
private static Stream<Arguments> nonPalindromeString() {
return Stream.of(
Arguments.of("hello"),
Arguments.of("race a car")
);
}
My solution is quite simple. There’re two pointers left and right as below:
public static boolean isStringPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
String stringLowerCase = s.toLowerCase();
while (left < right) {
char leftChar = stringLowerCase.charAt(left);
char rightChar = stringLowerCase.charAt(right);
if (!Character.isLetterOrDigit(leftChar)) {
left++;
} else if (!Character.isLetterOrDigit(rightChar)) {
right--;
} else if (leftChar != rightChar) {
return false;
} else {
right--;
left++;
}
}
return true;
}
Day 13: Aug 07 2023 – Reverse Integer
Difficulty Level: Medium
It should pass below test cases:
private static Stream<Arguments> inputExpectedOutput() {
return Stream.of(
Arguments.of(0, 0),
Arguments.of(-12345, -54321),
Arguments.of(12345, 54321),
// Should return zero when the reversed integer exceeds the integer limit
Arguments.of(1534236469, 0)
);
}
My solution is quite similar to the previous one Palindrome Number :
public static int reverseInteger(int x) {
int reverse = 0;
while (x != 0) {
if (reverse > Integer.MAX_VALUE / 10 || reverse < Integer.MIN_VALUE / 10) {
return 0;
}
int digit = x % 10;
reverse = reverse * 10 + digit;
x = x / 10;
}
return reverse;
}
Day 12: Aug 05 2023 – Palindrome Number
Difficulty Level: Easy
It should pass below test cases:
@ParameterizedTest
@MethodSource("palindromeNumbers")
@DisplayName("Should return true when the input is a palindrome number")
void isPalindromeWhenInputIsPalindromeNumber(int input) {
assertTrue(Palindrome.isPalindrome(input));
}
@ParameterizedTest
@MethodSource("nonPalindromeNumbers")
@DisplayName("Should return false when the input is not a palindrome number")
void isPalindromeWhenInputIsNotPalindromeNumber(int input) {
assertFalse(Palindrome.isPalindrome(input));
}
private static Stream<Arguments> palindromeNumbers() {
return Stream.of(
Arguments.of(121),
Arguments.of(1112111),
Arguments.of(11),
Arguments.of(0),
Arguments.of(9)
);
}
private static Stream<Arguments> nonPalindromeNumbers() {
return Stream.of(
Arguments.of(12345),
Arguments.of(-121),
Arguments.of(123)
);
}
My initial solution is where the time complexity is O(n) and space Complexity is O(n) comes from the space required to store the string representation of the integer x (n is the number of digits in the integer):
public static boolean isPalindrome(int x) {
if (x < 0) {
return false;
}
int left = 0;
String s = String.valueOf(x);
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
In the above challenge, I was thinking about how I can improve it. First of all, the given input is an integer, then the bottleneck is the conversion of the integer to a string. So let’s consider if there’s a way to directly manipulate the digits of the integer without converting it to a string. That’s why I come up with this solution:
public static boolean isPalindromeMath(int x) {
if (x < 0) {
return false;
}
int initial = x;
int temp = 0;
while (x > 0) {
int digit = x % 10;
temp = temp * 10 + digit;
x /= 10;
}
return initial == temp;
}
By doing so, the time complexity is O(log10(x)) and space complexity is reduced to O(1).
Day 11: Aug 04 2023 – Two Sum
Difficulty Level: Easy
It should pass below test cases:
private static Stream<Arguments> inputExpectedOutput() {
return Stream.of(
Arguments.of(new int[]{2, 7, 11, 15}, 9, new int[]{0, 1}),
Arguments.of(new int[]{3, 2, 4}, 6, new int[]{1, 2}),
Arguments.of(new int[]{3, 3}, 6, new int[]{0, 1})
);
}
My solution is simple, use a HashMap to keep track of the index. Time complexity is O(n).
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> indexByNum = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int remain = target - nums[i];
if (indexByNum.containsKey(remain)) {
return new int[]{indexByNum.get(remain), i};
}
indexByNum.put(nums[i], i);
}
return new int[2];
}
Day 10: Aug 03 2023 – Contains Duplicate
Difficulty Level: Easy
It should pass below test cases:
@ParameterizedTest
@MethodSource("inputExpectedOutput")
void testContainsDuplicate(int[] nums, boolean expected) {
boolean result = containsDuplicate(nums);
assertEquals(expected, result);
}
private static Stream<Arguments> inputExpectedOutput() {
return Stream.of(
Arguments.of(new int[]{1, 2, 3, 4, 5, 1}, true),
Arguments.of(new int[]{1, 1, 1, 3, 3, 4, 3, 2, 4, 2}, true),
Arguments.of(new int[]{}, false),
Arguments.of(new int[]{1, 2, 3, 4, 5}, false)
);
}
My solution is simple, just add a HashSet to check duplication. Time complexity is O(n).
public static boolean containsDuplicate(int[] nums) {
Set<Integer> temp = new HashSet<>();
for (int num : nums) {
if (temp.contains(num)) {
return true;
} else {
temp.add(num);
}
}
return false;
}
Day 9: Aug 02 2023 – Length of Last Word
Difficulty Level: Easy
It should pass below test cases:
@ParameterizedTest
@MethodSource("inputExpectedOutput")
void testLengthOfLastWord(String input, int expected) {
int actual = lengthOfLastWord(input);
assertEquals(expected, actual);
}
private static Stream<Arguments> inputExpectedOutput() {
return Stream.of(
Arguments.of("", 0),
Arguments.of("Hello World", 5),
Arguments.of(" fly me to the moon ", 4),
Arguments.of("luffy is still joyboy", 6)
);
}
My solution:
public static int lengthOfLastWord(String s) {
int i = s.length() - 1;
int lengthLastWord = 0;
while (i >= 0) {
if (s.charAt(i) == ' ' && i != s.length() - 1 && s.charAt(i + 1) != ' ') return lengthLastWord;
if (s.charAt(i) != ' ') {
lengthLastWord++;
}
i--;
}
return lengthLastWord;
}
The time complexity of the provided lengthOfLastWord method is O(n), where n is the length of the input string s.
Day 8: Aug 01 2023 – Search Insert Position
Difficulty Level: Easy
It should pass below test cases:
@ParameterizedTest
@MethodSource("arrayTargetExpectedIndex")
void testSearchInsert(int[] nums, int target, int expectedIndex) {
int actual = searchInsert(nums, target);
assertEquals(expectedIndex, actual);
}
private static Stream<Arguments> arrayTargetExpectedIndex() {
return Stream.of(
Arguments.of(new int[]{1, 3, 5, 6}, 5, 2),
Arguments.of(new int[]{1, 3, 5, 6}, 2, 1),
Arguments.of(new int[]{1, 3, 5, 6}, 0, 0),
Arguments.of(new int[]{1, 3, 5, 6}, 7, 4)
);
}
My initial solution uses Linear Search with time complexity O(n) where n is the length of the input array.
public static int searchInsert(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i;
}
if (i == 0 && target < nums[0]) return 0;
if (i > 0 && target > nums[i - 1] && target < nums[i]) {
return i;
}
}
return nums.length;
}
Given that the list provided is sorted, it would be more efficient to apply a binary search with a time complexity of O(log n). Let’s try the binary search implementation!
public static int searchInsertBinarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (right >= left) {
int mid = (right + left) / 2;
if (nums[mid] == target) return mid;
if (target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
Now, the time complexity of O(log n), this approach is a more efficient option, particularly when dealing with large input arrays.
Day 7: July 29 30 2023 – Longest Substring Without Repeating Characters
Difficulty Level: Medium
It should pass below test cases:
class LongestSubstringTest {
@ParameterizedTest
@MethodSource("inputExpected")
void testFindLengthOfLongestSubstring(String input, int expectedInt) {
int actual = lengthOfLongestSubstring(input);
assertEquals(expectedInt, actual);
}
private static Stream<Arguments> inputExpected() {
return Stream.of(
Arguments.of("abcabcbb", 3),
Arguments.of("bbbbb", 1),
Arguments.of("dvdf", 3),
Arguments.of("abcdbaecd", 5),
Arguments.of("anviaj", 5),
Arguments.of("", 0),
Arguments.of(" ", 1),
Arguments.of("pwwkew", 3)
);
}
}
Below is my initial approach that used a sliding window approach with pointers left and right.
public static int lengthOfLongestSubstring(String s) {
StringBuilder temp = new StringBuilder();
int maxLength = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
// Check if the current character already exists in the `temp`.
// If it is not present, add to `temp`
// If presented, update starting position of the sliding window (left)
// to the next position after the first occurrence of the repeating character
// and update the substring
int k = temp.toString().indexOf(s.charAt(right));
if (k != -1) {
maxLength = Math.max(maxLength, temp.length());
left += k + 1;
temp = new StringBuilder(s.substring(left, right + 1));
continue;
}
temp.append(s.charAt(right));
}
return Math.max(maxLength, temp.length());
}
It can also be implemented using Set as below:
public static int lengthOfLongestSubstringHashSet(String s) {
int maxLength = 0;
int left = 0;
int right = 0;
int n = s.length();
Set<Character> charSet = new HashSet<>();
while (right < n) {
if (!charSet.contains(s.charAt(right))) {
charSet.add(s.charAt(right));
maxLength = Math.max(maxLength, right - left + 1);
right++;
} else {
charSet.remove(s.charAt(left));
left++;
}
}
return maxLength;
}
However, the above approach has a time complexity of O(n^2). So I think about a data structure that can be used to check for character presence is more efficient. That why I come up with HashMap to maintain character and index. Instead of maintaining a substring to hold the non-repeating characters, use a HashMap (charIndexes) to store the character’s index in the string.
public static int lengthOfLongestSubstringMap(String s) {
int n = s.length();
int maxLength = 0;
int left = 0;
Map<Character, Integer> charIndexes = new HashMap<>();
for (int right = 0; right < n; right++) {
char currentChar = s.charAt(right);
if (charIndexes.containsKey(currentChar)) {
left = Math.max(charIndexes.get(currentChar) + 1, left);
}
maxLength = Math.max(maxLength, right - left + 1);
charIndexes.put(currentChar, right);
}
return maxLength;
}
This optimized solution’s time complexity is O(n).
Day 6: July 28 2023 – Valid Parentheses
Difficulty Level: Easy
It should pass below test cases:
class ValidParenthesesTest {
@ParameterizedTest
@MethodSource("inputExpectedOutput")
void testIsValidParentheses(String string, boolean expected) {
assertEquals(expected, ValidParentheses.isValid(string));
}
private static Stream<Arguments> inputExpectedOutput() {
return Stream.of(
Arguments.of("{[()]}", true),
Arguments.of(")}]", false),
Arguments.of("((({[", false),
Arguments.of("()[]{}", true)
);
}
}
My solution:
/**
* Check Valid Parentheses
* Open brackets must be closed by the same type of brackets.
* Open brackets must be closed in the correct order.
* Every close bracket has a corresponding open bracket of the same type.
*
* @param s - containing just the characters '(', ')', '{', '}', '[' and ']'
* @return true - if the input string is valid. Otherwise false
*/
public static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> brackets = new HashMap<>();
brackets.put('(', ')');
brackets.put('[', ']');
brackets.put('{', '}');
for (Character character : s.toCharArray()) {
if (brackets.containsKey(character)) {
stack.push(character);
} else if (brackets.containsValue(character)) {
if (stack.isEmpty()) {return false;}
if (!Objects.equals(character, brackets.get(stack.pop()))) return false;
}
}
return stack.isEmpty();
}
This solution has a time complexity of O(n), as it iterates through the input string s, where n is the length of the input string, and each operation inside the loop is a constant time operation. (The stack.isEmpty(), brackets.containsKey(), brackets.containsValue(), stack.push(), stack.pop(), and brackets.get() all have constant time complexities O(1)).
Day 5: July 27 2023 – Merge Two Sorted Lists
Difficulty Level: Easy
Given a ListNode as a singly-linked list:
/**
* Definition for singly-linked list.
*/
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
So the list should be:
public static void main(String[] args) {
ListNode list1 = new ListNode(1, new ListNode(2, new ListNode(5)));
ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
ListNode mergedList = mergeTwoLists(list1, list2);
// Print merged list
while (mergedList != null) {
System.out.print(mergedList.val);
if (mergedList.next != null) {
System.out.print(",");
}
mergedList = mergedList.next;
}
}
Solution:
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val <= list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
Day 4: July 26 2023 – Remove Element
Difficulty Level: Easy
It should pass below test cases:
class RemoveElementTest {
@ParameterizedTest
@MethodSource("inputArrayValueExpectedOut")
void testRemoveElement(int[] nums, int val, int expectedInt) {
int actual = RemoveElement.removeElement(nums, val);
assertEquals(expectedInt, actual);
}
private static Stream<Arguments> inputArrayValueExpectedOut() {
return Stream.of(
Arguments.of(new int[]{2, 2, 2, 2, 2}, 2, 0),
Arguments.of(new int[]{2, 2, 2, 2, 2}, 2, 0),
Arguments.of(new int[]{3, 2, 2, 3}, 3, 2),
Arguments.of(new int[]{0, 1, 2, 2, 3, 0, 4, 2}, 2, 5)
);
}
}
Solution:
public static int removeElement(int[] nums, int val) {
int j = 0;
int i = 0;
while (i < nums.length) {
if (nums[i] != val) {
nums[j] = nums[i];
j++;
}
i++;
}
return j;
}
Day 3: July 25 2023 – Remove Duplicates from Sorted Array
Difficulty Level: Easy
It should pass below test cases:
class RemoveDuplicateSortedArrayTest {
@ParameterizedTest
@MethodSource("test")
void testFindDuplicateSortedArray(int[] input, int expectedInt) {
int actual = RemoveDuplicateSortedArray.removeDuplicates(input);
assertEquals(expectedInt, actual);
}
private static Stream<Arguments> test() {
return Stream.of(
Arguments.of(new int[]{1, 1, 2}, 2),
Arguments.of(new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}, 5)
);
}
}
Solution:
public static int removeDuplicates(int[] nums) {
int i = 0;
for (int num : nums) {
if (i == 0 || nums[i - 1] != num) {
nums[i] = num;
i++;
}
}
return i;
}
public static int removeDuplicates(int[] nums) {
int i = 0;
for (int num : nums) {
if (i == 0 || nums[i - 1] != num) {
nums[i] = num;
i++;
}
}
return i;
}
Day 2: July 24 2023 – Longest Common Prefix
Difficulty Level: Easy
Solution:
class Solution {
public String longestCommonPrefix(String[] strs) {
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
String word = strs[i];
prefix = getCommonPrefixBetweenTwoString(prefix, word);
}
return prefix;
}
private static String getCommonPrefixBetweenTwoString(String str1, String str2) {
while (str2.indexOf(str1) != 0) {
str1 = str1.substring(0, str1.length() - 1);
if (str1.isEmpty()) return "";
}
return str1;
}
}
Day 1: July 23 2023 – Find the Index of the First Occurrence in a String
Difficulty Level: Easy
It should be passed the test cases:
class IndexOfFirstOccurrenceTest {
@ParameterizedTest(name = "{index} {0}")
@MethodSource("string1String2ExpectedOutput")
void getIndexOfFirstOccurrenceWhenFirstStringIsEmpty(String name, String str1, String str2, int expected) {
int result = IndexOfFirstOccurrence.getIndexOfFirstOccurrence(str1, str2);
assertEquals(expected, result);
}
private static Stream<Arguments> string1String2ExpectedOutput() {
return Stream.of(
Arguments.of("Should return -1 when the first string is empty", "", "abc", -1),
Arguments.of("Should return -1 when the second string is not present in the first string", "leetcode", "leeto", -1),
Arguments.of("Should return -1 when the second string is not fully present in the first string", "aaa", "aaaa", -1),
Arguments.of("Should return 0 when the first string starts with the second string", "mississippi", "miss", 0),
Arguments.of("Should return the correct index", "mississippi", "issip", 4),
Arguments.of("Should return the correct index", "a", "a", 0),
Arguments.of("Should return the correct index", "hello world", "o", 4)
);
}
}
My initial solution is straightforward:
class Solution {
public static int getIndexOfFirstOccurrence1(String str1, String str2) {
Map<Integer, String> res = new HashMap<>();
int firstChar = str2.charAt(0);
for (int i = 0; i < str1.length(); i++) {
if (firstChar == str1.charAt(i) && (str1.length() - i >= str2.length())) {
String subString = str1.substring(i, i + str2.length());
res.put(i, subString);
}
}
for (Map.Entry<Integer, String> entry : res.entrySet()) {
if (entry.getValue().equals(str2)) {
return entry.getKey();
}
}
return -1;
}
}
Then I found Java supported this one. So the solution can be simplified:
public static int getIndexOfFirstOccurrence(String str1, String str2) {
return str1.indexOf(str2);
}