Problems and solution
Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
Input: nums = [2,7,11,15], target = 9 Output: [0,1]
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> numMap = new HashMap<>();
for(int i = 0 ; i < nums.length;i++ ){
int complement = target-nums[i];
if(numMap.containsKey(complement)){
return new int[]{numMap.get(complement),i};
}
numMap.put(nums[i],i);
}
return null;
}
}
83. Remove Duplicates from Sorted List
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Input: head = [1,1,2] Output: [1,2]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
// Store the original head to return it later
ListNode res = head;
while(// Traverse the list while both current node and next node are not null
while (head != null && head.next != null) {
if(// If current node and next node have the same value,
// skip the next node by pointing current's 'next' to the node after next.
if (head.val == head.next.val) {
head.next = head.next.next;
} else{else {
// If values are different, move to the next node
head = head.next;
}
}
// Return the original head of the updated list
return res;
}
}
82. Remove Duplicates from Sorted List II
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
// Create a dummy node that points to the head.
// This helps handle edge cases, such as when the first few nodes are duplicates.
ListNode dummy = new ListNode(0);
dummy.next = head;
// 'prev' will always point to the last node before a group of duplicates.
ListNode prev = dummy;
// 'curr' is used to traverse the list from the head.
ListNode curr = head;
// Traverse the list until 'curr' and 'curr.next' are both non-null.
// We need 'curr.next' to compare the current node's value with the next node's value.
while (curr != null && curr.next != null) {
// Check if the current node has the same value as the next one — indicates a duplicate.
if (curr.val == curr.next.val) {
// Move 'curr' forward until the value changes (i.e., skip all duplicates).
while (curr.next != null && curr.val == curr.next.val) {
curr = curr.next;
}
// Now 'curr' points to the last node of the duplicate sequence.
// Skip all duplicates by linking 'prev.next' to the node after 'curr'.
prev.next = curr.next;
} else {
// If there's no duplication, just move 'prev' forward to 'curr'.
prev = prev.next;
}
// In both cases (whether duplicates were found or not), move 'curr' forward.
curr = curr.next;
}
// Return the next node after dummy, which is the head of the cleaned list.
return dummy.next;
}
}
Substring with concatenation of All words
You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.
For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words. Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.
Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation:
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words. The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ans = new ArrayList<Integer>();
Map<String,Integer> map = new HashMap<String,Integer>();
int wordCount = words.length;
int wordlength = words[0].length();
for(String word : words){
map.put(word,map.getOrDefault(word,0)+1);
}
for (int i = 0; i<= s.length() - wordlength*wordCount ;i++){
Map<String,Integer> copymap = new HashMap<String,Integer>(map);
for(int j = 0; j <wordCount;j++ ){
String subString = s.substring(i+j*wordlength,i+(j+1)*wordlength);
if(copymap.containsKey(subString)){
int count = copymap.get(subString);
if (count == 1){
copymap.remove(subString);
}else{
copymap.put(subString,count-1);
}
if (copymap.isEmpty()){
ans.add(i);
break;
}
}
else{
break;
}
}
}
return ans;
}
}
Optimised code
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ans = new ArrayList<>();
int wordCount = words.length;
int wordLength = words[0].length();
int stringLength = s.length();
Map<String,Integer> origMap = new HashMap<String,Integer>();
for(String word : words){
origMap.put(word,origMap.getOrDefault(word,0)+1);
}
for(int offset = 0; offset < wordLength; offset++){
Map<String,Integer> currMap = new HashMap<String,Integer>();
int start = offset;
int count = 0;
for(int end = offset; (end + wordLength) <= stringLength; end += wordLength){
String currWord = s.substring(end,end + wordLength);
if(origMap.containsKey(currWord)){
currMap.put(currWord,currMap.getOrDefault(currWord,0)+1);
count += 1;
while(currMap.get(currWord)>origMap.get(currWord)){
String startword = s.substring(start,start + wordLength);
currMap.put(startword,currMap.get(startword)-1);
start +=wordLength;
count-=1;
}
if(wordCount == count){
ans.add(start);
}
}
else{
count=0;
currMap.clear();
start = end+ wordLength;
}
}
}
return ans;
}
}