15 Jun 2021
In this blog I’ll be posting the codes (C++) and hints for the Linked List related questions. You can find the link to the curated Blind-75 link here.
Problem Given the head of a singly linked list, reverse the list, and return the reversed list.
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
ListNode* nxt = head;
while(nxt!=NULL){
nxt = nxt ->next;
curr->next = prev;
prev = curr;
curr = nxt;
}
return prev;
}
};
Problem Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Hint: Two pointer method
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==NULL)
return false;
ListNode* slow = head;
ListNode* fast = head->next;
while(slow!=fast){
if(fast==NULL || fast->next==NULL)
return false;
slow = slow ->next;
fast = fast->next->next;
}
return true;
}
};
Problem Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Hint: Recursion
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* result = NULL;
if(l1==NULL){
return l2;
}
if(l2==NULL){
return l1;
}
if(l1->val <= l2->val){
result = l1;
result->next = mergeTwoLists(l1->next, l2);
}
else{
result = l2;
result->next = mergeTwoLists(l1, l2->next);
}
return result;
}
};
Problem Given the head of a linked list, remove the nth node from the end of the list and return its head.
Hint: Two pointer method
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* fast = head;
ListNode* slow = head;
while(n--)
fast = fast->next;
if(fast==NULL)
return head->next;
while(fast->next!=NULL){
fast=fast->next;
slow=slow->next;
}
slow->next= slow->next->next;
return head;
}
};
Problem You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Hint: Using the penultimate node to form the connections between different nodes
class Solution {
public:
void reorderList(ListNode* head) {
if(head==NULL || head->next==NULL || head->next->next==NULL)
return;
ListNode* p = head;
while(p->next->next!=NULL){
p=p->next;
}
p->next->next = head->next;
head->next = p->next;
p->next=NULL;
reorderList(head->next->next);
}
};
07 Jun 2021
In this blog I’ll be posting the codes (C++) and hints for the Bitwise manipulation related questions. You can find the link to the curated Blind-75 link here.
Before that, here’s a few resources that helped me solve these questions!
Problem Given two integers a and b, return the sum of the two integers without using the operators + and -.
Hint: Using the logic of a Half adder (AND and XOR gates for carry and sum).
class Solution {
public:
int getSum(int a, int b) {
if (b==0) return a;
int sum = a^b; // finding the sum
int carry = (unsigned int)(a & b)<<1; // finding the carry
return getSum(sum, carry);
}
};
Problem Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
Hint: Checking for the right most bit and then doing right shift.
class Solution {
public:
int hammingWeight(uint32_t n) {
int count =0;
while(n>0){
count = count + (n&1);
n = n>>1;
}
return count;
}
};
Problem Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Hint: Calculating the number of 1s using the same logic from previous question.
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans;
for(int i=0; i<n+1; i++){
if(i==0)
ans.push_back(0);
else{
int temp = i;
int count = 0;
while(temp>0){
count += (temp&1);
temp= temp>>1;
}
ans.push_back(count);
}
}
return ans;
}
};
Problem Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Hint: Using the property of XOR that a ^ a = 0.
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ans = 0;
for(int i=0; i<nums.size(); i++){
int temp = nums[i]^i;
ans = ans ^ temp;
}
return ans^nums.size();
}
};
Problem Reverse bits of a given 32 bits unsigned integer.
Hint: Fixing the right most bit in the answer from the number and then shifting the answer to left and given number to right.
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
int ans = 0;
for(int i=0; i<32; i++){
ans= ans<<1;
ans= ans|(n&1);
n = n>>1;
}
return ans;
}
};
Thats all for now! I’m always up for a conversation, you can email me - either
about a blog post or anything else.
06 Jun 2021
In this blog I’ll be posting the codes (C++) and hints for the Array related questions. You can find the link to the curated Blind-75 link here.
Problem Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Hint: Iterating through the array
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
for(int i=0; i<nums.size(); i++){
for(int j=i+1;j<nums.size(); j++){
if(nums[i]+nums[j]==target){
ans.push_back(i);
ans.push_back(j);
}
}
}
return ans;
}
};
Problem You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Hint : Finding the minimum and maximum such that profit is maximized
class Solution {
public:
int maxProfit(vector<int>& prices) {
int mi = INT_MAX;
int profit = 0;
int n=prices.size();
for(int i=0; i<n; i++){
mi = min(mi,prices[i]);
profit = max(profit,(prices[i]-mi));
}
return profit;
}
};
Problem Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Hint : Using hashmap for optimization
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_map<int,bool> c;
for(int i=0; i<nums.size(); i++){
pair<int,bool> p(nums[i],true);
if(c.find(nums[i])!=c.end())
return true;
else
c.insert(p);
}
return false;
}
};
Problem Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.
Hint : using dynamic programming, we move in both directions from the beginning and the end
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> dp(nums.size(),1);
int left = 1, right = 1;
for(int i=0, j=nums.size()-1; i<nums.size(),j>=0; i++,--j){
dp[i]*=left;
dp[j]*=right;
left*=nums[i];
right*=nums[j];
}
return dp;
}
};
Problem Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Hint : Cadanes algorithm, watch this video for reference
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int meh = 0, msf = INT_MIN;
for(int i=0; i<nums.size(); i++){
meh = meh + nums[i];
if(meh < nums[i])
meh = nums[i];
if(msf < meh)
msf = meh;
}
return msf;
}
};
Problem Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product. It is guaranteed that the answer will fit in a 32-bit integer. A subarray is a contiguous subsequence of the array.
Hint : Here if we want to find the max product we need to calculate both maximum and minimum at each step because when minimum gets multiplied by another negative number it might become maximum.
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
int cmax = nums[0];
int pmin = nums[0];
int pmax = nums[0];
int product = nums[0];
int cmin;
for(int i=1; i<n; i++){
cmax = max(pmin * nums[i],max(pmax * nums[i], nums[i]));
cmin = min(pmin * nums[i],min(pmax * nums[i], nums[i]));
product = max(cmax,product);
pmax = cmax;
pmin = cmin;
}
return product;
}
};
Problem Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Hint : Important thing to understand is that a[0] will be greater than a[n-1], and so play with that
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
if(n==1)
return nums[0];
int s=0;
int e=n-1;
int mid;
while(s<e){
if(nums[s] < nums[e])
return nums[s];
mid = s+ ((e-s)/2);
if(nums[mid] >= nums[s])
s = mid + 1;
else
e = mid;
}
return nums[s];
}
};
Problem There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Hint : Here we need to check whether the first or the 2nd part of the array is sorted or not and make the further sub divisions accordingly
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int l=0;
int r = n-1;
int mid;
while(l<=r){
mid = l + ((r-l)/2);
if(nums[mid]==target)
return mid;
if(nums[l] <= nums[mid])
{
if(nums[mid]>=target && target>=nums[l])
r=mid-1;
else
l = mid+1;
}
else{
if(nums[mid]<=target && nums[r]>=target)
l=mid+1;
else
r=mid-1;
}
}
return -1;
}
};
Problem Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Hint : similar to 2 pointer method but we need to take care of duplicates
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = (int)nums.size()-2;
vector<vector<int>> ans;
sort(nums.begin(),nums.end());
for(int i=0 ;i<(int)nums.size()-2; i++){
if(i==0 || (i>0 && nums[i-1]!=nums[i])){
int sum = 0 - nums[i];
int low = i+1;
int high =(int)nums.size()-1;
while(low<high){
if(nums[low]+nums[high]==sum){
ans.push_back({nums[i],nums[low],nums[high]});
while(low<high && nums[low]==nums[low+1]) low++;
while(low<high && nums[high]==nums[high-1]) high--;
low++;
high--;
}
else if(nums[low]+nums[high]<sum){
low++;
}
else{
high--;
}
}
}
}
return ans;
}
};
Problem 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 the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.
Hint : we can optimise the length and using 2 pointer and move in the direction which gives higher area while having the width high
class Solution {
public:
int maxArea(vector<int>& height) {
int w = height.size()-1;
int l =0;
int r = w;
int area=0;
int h;
while(l<r){
h = min(height[l],height[r]);
int temp = h * w;
area = max(area,temp);
if(height[l] < height[r])
l = l+1;
else
r = r-1;
w--;
}
return area;
}
};
05 Jun 2021
hello world
It only felt apt to name the first blog to be hello world. This is going to be a quick blog post about why this blog and what all I’m planning to post in the near future. But, before that, Hi, I am Hetav M., currently a computer science rising junior and welcome to my blog.
Strengths: baking, technology, and knowing how to use code from stack overflow
Weaknesses: free food samples, dogs, and coming up with lists of more than three items
Why this blog?
Putting my work out there will make me more accountable and also just help me document my journey!
What I expect to post?
Interesting projects I am working on, leetcode solutions and my book recommendations!
Thats all for now! I’m always up for a conversation, you can email me - either about a blog post or anything else.