Earliest Second to Mark Indices I | Detailed Intuition | Leetcode Weekly Contest 386 | Leetcode 3048
103iPad PDF Notes - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-3048-Earliest%20Second%20to%20Mark%20Indices%20I.pdf
Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 29th Video of our Playlist "Greedy : Popular Interview Problems".
In this video we will try to solve a very good Greedy + BInary Search based problem : Earliest Second to Mark Indices I | Leetcode 3048
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Earliest Second to Mark Indices I | Detailed Intuition | Leetcode Weekly Contest 386 | Problem 3 | Leetcode 3048
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Greedy/Earliest%20Second%20to%20Mark%20Indices%20I.cpp
Leetcode Link : https://leetcode.com/problems/earliest-second-to-mark-indices-i/description/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Approach Summary :
Approach-1: Brute Force
Time Complexity (T.C): O(m * (m + n * log(n)))
Space Complexity (S.C): O(n)
Description:
The isValid function checks the validity of marking indices up to a given second using nested loops.
The main function iterates through each second and checks if it is a valid time to mark indices.
The time complexity is high due to the nested loops and sorting in the map.
Approach-2: Binary Search on Answer
Time Complexity (T.C): O(log(m) * (m + n * log(n)))
Space Complexity (S.C): O(n)
Description:
The isValid function remains the same as in Approach-1.
The main function uses binary search to find the earliest second to mark indices.
It initializes a binary search range (time_left to time_right) and updates the result based on the validity of the mid-point time.
The time complexity is reduced by replacing the linear search with binary search, resulting in a more efficient solution.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
00:23 - Problem Explanation
12:02 - Most Important Example
19:28 - What we learned
22:53 - LastPosition with Example
37:08 - How did I think about Binary Search
45:39 - Code it up
55:14 - Time Complexity
57:05 - Binary Search
59:42 - Time Complexity of Binary Search Approach
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear