<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Pushan Mukhopadhyay on Medium]]></title>
        <description><![CDATA[Stories by Pushan Mukhopadhyay on Medium]]></description>
        <link>https://medium.com/@mukhopadhyaypushan42?source=rss-305d9dc4b292------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*GNRBS3IGQBdDq740fYUOPg.jpeg</url>
            <title>Stories by Pushan Mukhopadhyay on Medium</title>
            <link>https://medium.com/@mukhopadhyaypushan42?source=rss-305d9dc4b292------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 02:59:21 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@mukhopadhyaypushan42/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[The Cookie That Couldn’t Cross the Border - CrossOrigin does not support !!]]></title>
            <link>https://medium.com/@mukhopadhyaypushan42/the-cookie-that-couldnt-cross-the-border-crossorigin-does-not-support-45d32b6ee124?source=rss-305d9dc4b292------2</link>
            <guid isPermaLink="false">https://medium.com/p/45d32b6ee124</guid>
            <category><![CDATA[backend]]></category>
            <category><![CDATA[cookies]]></category>
            <category><![CDATA[mern-stack]]></category>
            <category><![CDATA[jwt-authentication]]></category>
            <category><![CDATA[frontend-development]]></category>
            <dc:creator><![CDATA[Pushan Mukhopadhyay]]></dc:creator>
            <pubDate>Fri, 17 Oct 2025 14:48:37 GMT</pubDate>
            <atom:updated>2025-10-17T14:48:37.516Z</atom:updated>
            <content:encoded><![CDATA[<h3>The Cookie That Couldn’t Cross the Border 🍪🚫- CrossOrigin does not support !!</h3><p>Hey everyone!</p><p>I’m writing after a long time — hope you’re all doing great and staying caffeinated ☕.</p><p>So, recently I’ve been working on a <strong>side project built with the MERN stack</strong>, and like most of us, I decided to use <strong>cookies</strong> for managing user sessions.</p><p>Simple idea, right? Store the JWT token in a cookie on the client side and let the browser handle everything securely.</p><p>But… the moment I deployed my <strong>backend on Render</strong> and <strong>frontend on Vercel</strong>, things went <em>south.</em></p><p>Login worked fine <strong>locally</strong>, but on production, no cookie was being sent, no authentication persisted, and every protected API said:</p><blockquote><em>“Who are you again?”</em></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kAx0EBQF89IKuxIuU0kLZg.jpeg" /></figure><h3><strong>🧩 What’s Actually Happening?</strong></h3><p>When your frontend and backend are hosted on <strong>different domains, </strong>any communication between them becomes a <strong>cross-origin request</strong>.</p><blockquote>Our browser sees this like</blockquote><blockquote>“Origin A → sending request → Origin B”</blockquote><p>In simple language</p><blockquote>Cookies Got Trust Issues: Why Your Tokens Don’t Travel Anymore 🍪🔒</blockquote><p>But why???</p><p><strong><em>Modern browsers (Chrome, Firefox, Safari, Edge)</em></strong><em> don’t automatically allow cookies to be shared across different origins for security reasons.</em></p><h3><strong>🔐 The Reason: SameSite Cookie Policy</strong></h3><p>A few years back, Chrome (and other browsers soon followed) introduced a stricter rule called the <strong>SameSite cookie policy</strong>.<br> This was done to improve web security and privacy — particularly to fight <strong>Cross-Site Request Forgery (CSRF)</strong> and <strong>tracking abuse</strong>.</p><p>Each cookie can now have a SameSite attribute that controls <em>when it’s sent</em>:</p><p><strong>Strict</strong> — Cookies only sent for requests from the same domain. (Maximum security, zero cross-site sharing.)</p><p><strong>Lax — </strong>Cookies are sent for safe top-level navigations (like GETs) but blocked for POST, PUT, etc.</p><p><strong>None — </strong>Cookies <em>can</em> be sent across domains, but only if Secure is also set (meaning HTTPS).</p><p>So if you didn’t explicitly set your cookie as:</p><pre>res.cookie(&quot;token&quot;, token, {<br>  httpOnly: true,<br>  secure: true,<br>  sameSite: &quot;None&quot;,<br>});</pre><p>then your browser silently <strong>drops</strong> it during cross-origin requests.</p><h3><strong>🚀 Now, in my case,</strong></h3><pre>const loginController = async (req, res) =&gt; {<br>  try {<br>    const { email, password } = req.body;<br><br>    if (!email || !password) {<br>      return res<br>        .status(400)<br>        .json({ message: &quot;Please provide email and password&quot; });<br>    }<br><br>    const user = await User.findOne({ email });<br>    if (!user) {<br>      return res.status(400).json({ message: &quot;User not found&quot; });<br>    }<br><br>    const isPasswordCorrect = await bcrypt.compare(password, user.password);<br>    if (!isPasswordCorrect) {<br>      return res.status(400).json({ message: &quot;Invalid credentials&quot; });<br>    }<br>    const token = jwt.sign(<br>      { id: user._id, email: user.email },<br>      process.env.JWT_SECRET,<br>      { expiresIn: &quot;7d&quot; }<br>    );<br><br>    res.status(200).json({<br>      message: &quot;Login successful&quot;,<br>      token,<br>      user: {<br>        id: user._id,<br>        fullName: user.fullName,<br>        email: user.email,<br>        githubConnected: user.githubConnected,<br>        profilePicture: user.profilePicture,<br>      },<br>    });<br>  } catch (error) {<br>    console.log(&quot;Error in login controller&quot;, error);<br>    res.status(500).json({ message: &quot;Internal Server Error&quot; });<br>  }<br>};</pre><p>this is a simple login controller and</p><pre>const signupController = async (req, res) =&gt; {<br>  try {<br>    const { fullName, email, password } = req.body;<br><br>    if (!fullName || !email || !password) {<br>      return res.status(400).json({ message: &quot;Please provide all the fields&quot; });<br>    }<br><br>    const isexistingUser = await User.findOne({ email });<br><br>    if (isexistingUser) {<br>      return res.status(400).json({ message: &quot;User already exists&quot; });<br>    }<br><br>    const hashedPassword = await passwordEncryption(password);<br><br>    const newUser = new User({<br>      fullName,<br>      email,<br>      password: hashedPassword,<br>    });<br><br>    await newUser.save();<br><br>    const token = jwt.sign(<br>      { id: newUser._id, email: newUser.email },<br>      process.env.JWT_SECRET,<br>      { expiresIn: &quot;7d&quot; }<br>    );<br><br>    res.status(201).json({<br>      message: &quot;User created successfully&quot;,<br>      token,<br>      user: {<br>        id: newUser._id,<br>        fullName: newUser.fullName,<br>        email: newUser.email,<br>      },<br>    });<br>  } catch (error) {<br>    console.log(&quot;Error in signup controller&quot;, error);<br>    res.status(500).json({ message: &quot;Facing issue while signup&quot; });<br>  }<br>};</pre><p>This is a signup controller.</p><pre>app.use(cors({<br>  origin: process.env.FRONTEND_URL,<br>  credentials: true,<br>  methods: [&quot;GET&quot;, &quot;POST&quot;, &quot;PUT&quot;, &quot;DELETE&quot;, &quot;OPTIONS&quot;],<br>  allowedHeaders: [&quot;Content-Type&quot;, &quot;Authorization&quot;],<br>}));</pre><p>Here I am using a simple way to sign a JWT token and set it as a cookie.</p><p>And in the frontend part, I also have a proper axios setup</p><pre>const axiosInstance = axios.create({<br>    baseURL: baseUrl,<br>    withCredentials: true,<br>})<br><br>export default axiosInstance;</pre><p>It works fine in localhost, but things get …. in production.</p><blockquote>Frontend — Vercel</blockquote><blockquote>Backend — Render</blockquote><p>No cookie is set. After logging in, it simply shows a toast message</p><p>“login successful,” but in the console, it shows “unauthorized.”</p><p>(Cause I am using an endpoint to get the current user)</p><h3><strong>🥳 The Solution</strong></h3><p>After finding ChatGPT, StackOverflow, Vercel community, and Reddit</p><p>nothing works for me</p><blockquote>“Vercel Loves Render… But the Browser Said No 💔”</blockquote><h4><strong>Now I am using</strong> “currently using <strong>JWT in headers (Bearer token)</strong> instead of cookies”</h4><p><strong>🧱 1. Backend (Express.js)</strong></p><pre>const cors = require(&quot;cors&quot;);<br><br>app.use(<br>  cors({<br>    origin: [&quot; &quot;], // your frontend<br>    methods: [&quot;GET&quot;, &quot;POST&quot;, &quot;PUT&quot;, &quot;DELETE&quot;],<br>    credentials: true,<br>    allowedHeaders: [&quot;Content-Type&quot;, &quot;Authorization&quot;],<br>  })<br>);</pre><p>Even if you’re using tokens in headers, the Authorization header must be allowed explicitly in CORS — otherwise, the browser silently blocks it.</p><p><strong>🧠 2. Middleware</strong></p><pre>const jwt = require(&quot;jsonwebtoken&quot;);<br>const User = require(&quot;../model/User&quot;);<br><br>const isLoggedIn = async (req, res, next) =&gt; {<br>  try {<br>    const authHeader = req.headers.authorization;<br>    if (!authHeader?.startsWith(&quot;Bearer &quot;)) {<br>      return res.status(401).json({ message: &quot;Unauthorized - Missing token&quot; });<br>    }<br><br>    const token = authHeader.split(&quot; &quot;)[1];<br>    const decoded = jwt.verify(token, process.env.JWT_SECRET);<br><br>    const user = await User.findById(decoded.id).select(<br>      &quot;fullName email githubConnected profilePicture&quot;<br>    );<br>    if (!user) return res.status(404).json({ message: &quot;User not found&quot; });<br><br>    req.user = user;<br>    next();<br>  } catch (err) {<br>    console.error(&quot;❌ Auth middleware error:&quot;, err.message);<br>    return res.status(401).json({ message: &quot;Invalid or expired token&quot; });<br>  }<br>};<br><br>module.exports = isLoggedIn;</pre><p><strong>🪄 3. Login &amp; Signup Controllers</strong></p><pre>res.status(200).json({<br>  message: &quot;Login successful&quot;,<br>  token,<br>  user: {<br>    .<br>    .<br>    .<br>  },<br>});</pre><p>We have to send “<strong>token”</strong> in JSON response.</p><p>⚛<strong>️ 4. Frontend Axios Setup</strong></p><pre>import axios from &quot;axios&quot;;<br><br>const baseURL = import.meta.env.VITE_BASEURL;<br><br>const axiosInstance = axios.create({<br>  baseURL,<br>  withCredentials: true, // not mandatory for Bearer but keeps compatibility<br>});<br><br>axiosInstance.interceptors.request.use((config) =&gt; {<br>  const token = localStorage.getItem(&quot;token&quot;);<br>  if (token) {<br>    config.headers.Authorization = `Bearer ${token}`;<br>  }<br>  return config;<br>});<br><br>export default axiosInstance;</pre><p>✅ This ensures:</p><ul><li>Every API call automatically includes your token.</li><li>If token doesn’t exist, API will naturally fail with 401.</li></ul><h4>🧾<strong>Login example api</strong></h4><pre>export const login = async (loginData) =&gt; {<br>  const response = await axiosInstance.post(&quot;/auth/login&quot;, loginData);<br>  const token = response.data.token;<br>  localStorage.setItem(&quot;token&quot;, token); <br>  return response.data;<br>};<br><br>// logout<br><br>export const logout = () =&gt; {<br>  localStorage.removeItem(&quot;token&quot;);<br>};</pre><p><strong>🧪 7. Verify It Works (Quick Test)</strong></p><p>Open <strong>Browser DevTools → Network tab</strong>:</p><ol><li>Log in → See a POST /auth/login → Response contains { token }.</li><li>On any protected route → Request headers should include:</li></ol><pre>Authorization: Bearer &lt;token&gt;</pre><ol><li>Backend logs should print decoded user (if you console it inside middleware).</li><li>If yes — your authentication is working perfectly ✅</li></ol><h3>🚀 Optional Improvement</h3><p>To prevent token theft from localStorage, you can store it in <strong>memory</strong> using something like <strong>zustand</strong>, <strong>React Context</strong>, or <strong>Redux</strong> — this way, it’s wiped on page reload but safer for sensitive tokens.</p><p><strong>TL;DR:</strong></p><blockquote><em>Use Bearer tokens in headers, configure CORS with </em><em>allowedHeaders: [&quot;Authorization&quot;], and store tokens in localStorage.<br> No cookies = No cross-origin pain = Works 100% guaranteed 🎯</em></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=45d32b6ee124" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solve DP problems like butter !!!]]></title>
            <link>https://medium.com/@mukhopadhyaypushan42/solve-dp-problems-like-butter-c6022e39f422?source=rss-305d9dc4b292------2</link>
            <guid isPermaLink="false">https://medium.com/p/c6022e39f422</guid>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[memorization-techniques]]></category>
            <category><![CDATA[competitive-coding]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Pushan Mukhopadhyay]]></dc:creator>
            <pubDate>Sat, 27 Apr 2024 18:36:11 GMT</pubDate>
            <atom:updated>2024-04-27T18:36:11.455Z</atom:updated>
            <content:encoded><![CDATA[<p>So in the beginning phase, Dp is a nightmare for all.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/0*QmznMddgeUCbctnO" /></figure><p>So what is Dp???</p><blockquote><strong>Dynamic Programming (DP)</strong> is a method used in mathematics and computer science to solve complex problems by breaking them down into simpler subproblems. By solving each subproblem only once and storing the results, it avoids redundant computations, leading to more efficient solutions for a wide range of problems.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/0*igcpd122VCHETI7m.png" /></figure><h3>How Does Dynamic Programming (DP) Work?</h3><ul><li><strong>Identify Subproblems:</strong> Divide the main problem into smaller, independent subproblems.</li><li><strong>Store Solutions: </strong>Solve each subproblem and store the solution in a table or array.</li><li><strong>Build Up Solutions:</strong> Use the stored solutions to build up the solution to the main problem.</li><li><strong>Avoid Redundancy:</strong> By storing solutions, DP ensures that each subproblem is solved only once, reducing computation time.</li></ul><h3>7 Steps to solve a Dynamic Programming problem</h3><p>In the rest of this post, I will go over a recipe that you can follow to figure out if a problem is a “DP problem”, as well as to figure out a solution to such a problem. Specifically, I will go through the following steps:</p><ol><li>How to recognize a DP problem</li><li>Identify problem variables</li><li>Clearly express the recurrence relation</li><li>Identify the base cases</li><li>Decide if you want to implement it iteratively or recursively</li><li>Add memoization</li><li>Determine time complexity</li></ol><h3>Sample DP Problem</h3><p>For the purpose of having an example for abstractions that I am going to make, let me introduce a sample problem. In each of the sections, I will refer to the problem, but you could also read the sections independently of the problem.</p><h4>Problem statement:</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/0*OyT2ixkHrqdDnrR6" /></figure><p><em>In this problem, we’re on a crazy jumping ball, trying to stop, while avoiding spikes along the way.</em></p><h4>Here are the rules:</h4><p>1) You’re given a flat runway with a bunch of spikes in it. The runway is represented by a boolean array which indicates if a particular (discrete) spot is clear of spikes. It is True for clear and False for not clear.</p><p>Example array representation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/0*c5Vukk9qlrjKcPRR" /></figure><p>2) You’re given a starting speed S. S is a non-negative integer at any given point, and it indicates how much you will move forward with the next jump.</p><p>3) Every time you land on a spot, you can adjust your speed by up to 1 unit before the next jump.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/0*sIRhbYyMctAiFGG2" /></figure><p>4) You want to safely stop anywhere along the runway (does not need to be at the end of the array). You stop when your speed becomes 0. However, if you land on a spike at any point, your crazy bouncing ball bursts and it’s game over.</p><p><strong>The output of your function should be a boolean indicating whether we can safely stop anywhere along the runway.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/0*5hThObGO7lKIjKHQ.png" /></figure><h4>Step 1: How to recognize a Dynamic Programming problem</h4><p>First, let’s make it clear that DP is essentially just an optimization technique. DP is a method for solving problems by breaking them down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, instead of recomputing its solution, you simply look up the previously computed solution. This saves computation time at the expense of a (hopefully) modest expenditure in storage space.</p><p>Recognizing that a problem can be solved using DP is the first and often the most difficult step in solving it. What you want to ask yourself is whether your problem solution can be expressed as a function of solutions to similar smaller problems.</p><p>In the case of our example problem, given a point on the runway, a speed, and the runway ahead, we could determine the spots where we could potentially jump next. Furthermore, it seems that whether we can stop from the current point with the current speed depends only on whether we could stop from the point we choose to go to next.</p><p>That is a great thing, because by moving forward, we shorten the runway ahead and make our problem smaller. We should be able to repeat this process all the way until we get to a point where it is obvious whether we can stop.</p><blockquote><em>Recognizing a Dynamic Programming problem is often the most difficult step in solving it. Can the problem solution be expressed as a function of solutions to similar smaller problems?</em></blockquote><h4>Step 2: Identify problem variables</h4><p>Now we have established that there is some recursive structure between our subproblems. Next, we need to express the problem in terms of the function parameters and see which of those parameters are changing.</p><p>Typically in interviews, you will have one or two changing parameters, but technically this could be any number. A classic example of a one-changing-parameter problem is “determine an n-th Fibonacci number”. Such an example for a two-changing-parameters problem is “Compute edit distance between strings”. If you’re not familiar with these problems, don’t worry about it.</p><p>A way to determine the number of changing parameters is to list examples of several subproblems and compare the parameters. Counting the number of changing parameters is valuable to determine the number of subproblems we have to solve. It’s also important in its own right in helping us strengthen the understanding of the recurrence relation from step 1.</p><p>In our example, the two parameters that could change for every subproblem are:</p><ol><li><strong>Array position (P)</strong></li><li><strong>Speed (S)</strong></li></ol><p>One could say that the runway ahead is changing as well, but that would be redundant considering that the entire non-changing runway and the position (P) carry that information already.</p><p>Now, with these 2 changing parameters and other static parameters, we have the complete description of our sub-problems.</p><blockquote><em>Identify the changing parameters and determine the number of subproblems.</em></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*M1OrQTIPGk2dRF6x.jpg" /></figure><h4>Step 3: Clearly express the recurrence relation</h4><p>This is an important step that many rush through in order to get into coding. Expressing the recurrence relation as clearly as possible will strengthen your problem understanding and make everything else significantly easier.</p><p>Once you figure out that the recurrence relation exists and you specify the problems in terms of parameters, this should come as a natural step. How do problems relate to each other? In other words, let’s assume that you have computed the subproblems. How would you compute the main problem?</p><p>Here is how we think about it in our sample problem:</p><p>Because you can adjust your speed by up to 1 before jumping to the next position, there are only 3 possible speeds, and therefore 3 spots in which we could be next.</p><p>More formally, if our speed is S, position P, we could go from (S, P) to:</p><ol><li><strong>(S, P + S)</strong>; # if we do not change the speed</li><li><strong>(S — 1, P + S — 1)</strong>; # if we change the speed by -1</li><li><strong>(S + 1, P + S + 1)</strong>; # if we change the speed by +1</li></ol><p>If we can find a way to stop in any of the subproblems above, then we can also stop from (S, P). This is because we can transition from (S, P) to any of the above three options.</p><p>This is typically a fine level of understanding of the problem (plain English explanation), but you sometimes might want to express the relation mathematically as well. Let’s call a function that we’re trying to compute canStop. Then:</p><p><strong>canStop(S, P) = canStop(S, P + S) || canStop(S — 1, P + S — 1) || canStop(S + 1, P + S + 1)</strong></p><p>Woohoo, it seems like we have our recurrence relation!</p><blockquote><em>Recurrence relation: Assuming you have computed the subproblems, how would you compute the main problem?</em></blockquote><h4>Step 4: Identify the base cases</h4><p>A base case is a subproblem that doesn’t depend on any other subproblem. In order to find such subproblems, you typically want to try a few examples, see how your problem simplifies into smaller subproblems, and identify at what point it cannot be simplified further.</p><p>The reason a problem cannot be simplified further is that one of the parameters would become a value that is not possible given the <strong>constraints</strong> of the problem.</p><p>In our example problem, we have two changing parameters, S and P. Let’s think about what possible values of S and P might not be legal:</p><ol><li><strong>P should be within the bounds of the given runway</strong></li><li><strong>P cannot be such that runway[P] is false because that would mean that we’re standing on a spike</strong></li><li><strong>S cannot be negative, and a S==0 indicates that we’re done</strong></li></ol><p>Sometimes it can be a little challenging to convert assertions that we make about parameters into programmable base cases. This is because, in addition to listing the assertions if you want to make your code look concise and not check for unnecessary conditions, you also need to think about which of these conditions are even possible.</p><p>In our example:</p><ol><li><strong>P &lt; 0 || P &gt;= length of </strong>runway seems like the right thing to do. An alternative could be to consider m<em>aking</em><strong> P == end of </strong>runway a base case. However, it is possible that a problem splits into a subproblem which goes beyond the end of the runway, so we really need to check for inequality.</li><li>This seems pretty obvious. We can simply check <strong>if runway[P] is false<em>.</em></strong></li><li>Similar to #1, we could simply check for S &lt; 0 and S == 0. However, here we can reason that it is impossible for S to be &lt; 0 because S decreases by at most 1, so it would have to go through S == 0 case beforehand. Ther<strong>efore </strong>S == 0 is a sufficient base case for the S parameter.</li></ol><h4>Step 5: Decide if you want to implement it iteratively or recursively</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*IqfdB59p9HyZozR0" /></figure><h4>Step 6: Add memoization</h4><p><strong>Memoization</strong> is a technique that is closely associated with DP. It is used for storing the results of expensive function calls and returning the cached result when the same inputs occur again.</p><p>Why are we adding memoization to our recursion? We encounter the same subproblems which, without memoization, are computed repeatedly. Those repetitions very often lead to exponential time complexities.</p><p>In recursive solutions, adding memoization should feel straightforward. Let’s see why. Remember that memoization is just a cache of the function results. There are times when you want to deviate from this definition in order to squeeze out some minor optimizations, but treating memoization as a function result cache is the most intuitive way to implement it.</p><p>This means that you should:</p><ol><li>Store your function result into your memory before every <em>return</em> <em>statement</em></li><li>Look up the memory for the function result before you start doing any other computation</li></ol><h4>Step 7: Determine Time complexity</h4><p>There are some simple rules that can make computing time complexity of a dynamic programming problem much easier. Here are two steps that you need to do:</p><ol><li>Count the number of states — this will depend on the number of changing parameters in your problem</li><li>Think about the work done per each state. In other words, if everything else but one state has been computed, how much work do you have to do to compute that last state?</li></ol><p>In our example problem, the number of states is <strong>|P| * |S|,</strong> where</p><ul><li>P is the set of all positions (|P| indicates the number of elements in P)</li><li>S is the set of all speeds</li></ul><p>The work done per each state is O(1) in this problem because, given all other states, we simply have to look at 3 subproblems to determine the resulting state.</p><p>As we noted in the code before, |S| is limited by length of the runway (|P|), so we could say that the number of states is |P|² and because work done per each state is O(1), then the total time complexity is O(|P|²).</p><p>However, it seems that |S| can be further limited, because if it were really |P|, it is very clear that stopping would not be possible because you would have to jump the length of the entire runway on the first move.</p><p>So let’s see how we can put a tighter bound on |S|. Let’s call maximum speed S. Assume that we’re starting from position 0. How quickly could we stop if we were trying to stop as soon as possible and if we ignore potential spikes?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/0*rv5W8EhCb1npOVDu" /></figure><p>In the first iteration, we would have to come at least to the point (S-1), by adjusting our speed at zero by -1. From there we would at a minimum go by (S-2) steps forward, and so on.</p><p>For a runway of <strong>length L</strong>, the following has to hold:</p><p><strong>=&gt; (S-1) + (S-2) + (S-3) + ….+ 1 </strong>&lt; L</p><p><strong>=&gt; S*(S-1) / 2 </strong>&lt; L</p><p><strong>=&gt; S² — S — 2L </strong>&lt; 0</p><p>If you find roots of the above function, they will be:</p><p><strong>r1 = 1/2 + sqrt(1/4 + 2L) and r2 = 1/2 — sqrt(1/4 + 2L)</strong></p><p>We can write our inequality as:</p><p><strong>(S — r1) * (S — r2) &lt;</strong>; 0</p><p>Considering that S — r2 &gt; 0 for any S &gt; 0 and L &gt; 0, we need the following:</p><p><strong>S — 1/2 — sqrt(1/4 + 2L) &lt;</strong>; 0</p><p><strong>=&gt; S &lt; 1/2 + sqrt(1/4</strong> + 2L)</p><p>That is the maximum speed that we could possibly have on a runway of a length L. If we had a speed higher than that, we could not stop even theoretically, irrespective of the position of the spikes.</p><p>That means that the total time complexity depends only on the length of the runway L in the following form:</p><p>O(L * sqrt(L)) which is better than O(L²)</p><blockquote>O(L * sqrt(L)) is the upper bound on the time complexity</blockquote><p>The main thing is practicing the dp problems. Practice Practice Practice and keep practicing….</p><h4>Can practice these problems -&gt; <a href="https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/">DP</a></h4><p>Thank You</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c6022e39f422" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[7 Must Know JavaScript Tips & Tricks ]]></title>
            <link>https://medium.com/@mukhopadhyaypushan42/7-must-know-javascript-tips-tricks-905668e09f48?source=rss-305d9dc4b292------2</link>
            <guid isPermaLink="false">https://medium.com/p/905668e09f48</guid>
            <category><![CDATA[javascript-tips]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[javascript-frameworks]]></category>
            <category><![CDATA[javascript-scope]]></category>
            <category><![CDATA[javascript-development]]></category>
            <dc:creator><![CDATA[Pushan Mukhopadhyay]]></dc:creator>
            <pubDate>Wed, 31 Jan 2024 14:11:12 GMT</pubDate>
            <atom:updated>2024-01-31T14:11:12.241Z</atom:updated>
            <content:encoded><![CDATA[<p>Let’s have a look at <strong>7</strong> valuable tips and tricks found in the most popular language in the world, <strong>JavaScript</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*Zd6GzjNvtBMyUfxa" /></figure><h3>1. Destructuring with Parameters</h3><p>You can use <strong>object destructuring</strong> within function parameters. A popular use case for this would be something like event listeners, and gaining access to the target property on the event object.</p><pre>buttonElement.addEventListener(&quot;click&quot;, ({ target }) {<br>    // is the same as using e.target 👇<br>    console.log(target);<br>});</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/0*CX3E1LTsekgBW8bh.jpg" /></figure><h3>2. Deep Copy with JSON</h3><p>You may have heard of using object spread or Object.assign() to make <strong>shallow copies</strong> of an object, but did you know about using JSON to make <strong>deep copies?</strong></p><p>Simply convert an object to JSON using JSON.stringify() and then re-parse it using JSON.parse() to create a <strong>deep copy</strong>.</p><p>Just remember to only do this for simple objects, as doing it on large objects may raise performance issues.</p><pre>const person = {<br>    name: &quot;Dom&quot;,<br>    age: 28,<br>    skills: [<br>        &quot;Programming&quot;,<br>        &quot;Cooking&quot;,<br>        &quot;Tennis&quot;<br>    ]<br>};<br><br>const copied = JSON.parse(JSON.stringify(person));<br><br>// false 😎<br>console.log(person.skills === copied.skills);</pre><h3>3. Easy Defaults with OR</h3><p>I talk about this one a lot. Basically, you can use the <strong>logical OR operator</strong> (||) for defaults as opposed to using an <strong>if</strong> statement.</p><p>Alternatively, for stricter comparisons, you can take advantage of the nullish coalescing operator</p><p><strong>Old Code (using if statement — 4 lines)</strong></p><pre>let username = getUsername();<br><br>if (!username) {<br>    username = &quot;Dom&quot;;<br>}</pre><p><strong>New Code (using </strong><strong>|| - 1 line)</strong></p><pre>const username = getUsername() || &quot;Dom&quot;;</pre><pre>💬💬🗨️🗨️JavaScript was invented in 1995 by Brendan Eich in 10 days.</pre><p>The new code also means you can use const over let.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*IkqwrCbkJSowZBng.jpg" /></figure><h3>4. Advanced Array Searching</h3><p>Step aside, indexOf() and includes() because there&#39;s another method that allows for <strong>advanced</strong> array searching and it&#39;s called find().</p><p>The find() method allows you to pass in a <strong>test function</strong>. The first element within the array to pass the test function will be returned.</p><p>This makes for more useful array searching.</p><pre>const occupations = [<br>    &quot;Lawyer&quot;,<br>    &quot;Doctor&quot;,<br>    &quot;Programmer&quot;,<br>    &quot;Chef&quot;,<br>    &quot;Store Manager&quot;,<br>];<br><br>const result = occupations.find(o =&gt; o.startsWith(&quot;C&quot;));<br><br>// &quot;Chef&quot; 🧑‍🍳<br>console.log(result);</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*-o_J7ESo6zX8RoBA.jpeg" /></figure><h3>5. Remove Array Duplicates</h3><p>You may have heard of this one before, but there’s a really simple way to remove duplicates from an array using the Set data structure.</p><p>Basically, Set doesn&#39;t allow duplicate values. We can take advantage of that by turning an array into a Set, and then back into an array.</p><pre>const numbers = [5, 10, 5, 20];<br>const withoutDuplicates = Array.from(new Set(numbers));<br><br>// [5, 10, 20] 👇<br>console.log(withoutDuplicates);</pre><h3>6. Self-Invoking Functions</h3><p>This one is a classic. Self-invoking functions are functions that <strong>execute themselves</strong>. A common use case for these is to assign a variable or constant that requires complex logic.</p><pre>const someComplexValue = (() =&gt; {<br>    const a = 10;<br>    const b = 20;<br><br>    if (a &gt; b) {<br>        return a * b;<br>    }<br><br>    return b / a;<br>})();</pre><p>Of course, the above example is trivial but you can imagine the kind of complex code you may require to be within the self-invoking function.</p><h3>7. Array Copying with Spread</h3><p>Last on this list involves creating <strong>shallow</strong> copies of an array. We can do this using Spread (...).</p><pre>const numbers = [5, 19, 24, 36];<br>const numbersCopy = [...numbers];<br><br>// false<br>console.log(numbers === numbersCopy);</pre><p>Hope you understand this article.</p><blockquote>Stay Tune</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=905668e09f48" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Dutch national flag sorting problem]]></title>
            <link>https://medium.com/@mukhopadhyaypushan42/dutch-national-flag-sorting-problem-d7cd3a0625c9?source=rss-305d9dc4b292------2</link>
            <guid isPermaLink="false">https://medium.com/p/d7cd3a0625c9</guid>
            <category><![CDATA[sorting-algorithms]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[array-sorting]]></category>
            <category><![CDATA[coding]]></category>
            <dc:creator><![CDATA[Pushan Mukhopadhyay]]></dc:creator>
            <pubDate>Fri, 10 Nov 2023 10:46:04 GMT</pubDate>
            <atom:updated>2023-11-10T10:46:04.527Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1023/0*YuVXl2uqQh6JM3ba" /></figure><p>For this problem, your goal is to sort an array of 0, 1 and 2’s but you must do this in place, in linear time and without any extra space (such as creating an extra array). This is called the Dutch national flag sorting problem. For example, if the input array is [2,0,0,1,2,1] then your program should output [0,0,1,1,2,2] and the algorithm should run in <em>O</em>(<em>n</em>) time.</p><h3>Algorithm</h3><p>The solution to this algorithm will require 3 pointers to iterate throughout the array, swapping the necessary elements.</p><p>(1) Create a <strong>low</strong> pointer at the beginning of the array and a <strong>high</strong> pointer at the end of the array. (2) Create a <strong>mid</strong> pointer that starts at the beginning of the array and iterates through each element. (3) If the element at arr[mid] is a 2, then swap arr[mid] and arr[high] and decrease the <strong>high</strong> pointer by 1. (4) If the element at arr[mid] is a 0, then swap arr[mid] and arr[low] and increase the <strong>low</strong> and <strong>mid</strong> pointers by 1. (5) If the element at arr[mid] is a 1, don’t swap anything and just increase the <strong>mid</strong> pointer by 1.</p><p>This algorithm stops once the <strong>mid</strong> pointer passes the <strong>high</strong> pointer.</p><h3>Example</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/513/0*wSSvcutKwmJpm3Q8.jpg" /></figure><h3>Code</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CHuYTBEfeVrU9JCIwG9ttQ.png" /></figure><h3>Running time</h3><p>This algorithm runs in <em>O</em>(<em>n</em>) time because it only passes through the array once swapping the necessary elements in place.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d7cd3a0625c9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Master Theorem for TIME COMPLEXITY]]></title>
            <link>https://medium.com/@mukhopadhyaypushan42/master-theorem-for-time-complexity-14bb54ac3930?source=rss-305d9dc4b292------2</link>
            <guid isPermaLink="false">https://medium.com/p/14bb54ac3930</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[time-complexity]]></category>
            <category><![CDATA[master-theorem]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[sad]]></category>
            <dc:creator><![CDATA[Pushan Mukhopadhyay]]></dc:creator>
            <pubDate>Thu, 26 Oct 2023 09:23:01 GMT</pubDate>
            <atom:updated>2023-10-26T09:23:01.081Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*FGZjYu29rCrmZV3S" /></figure><p>The master method is a formula for solving recurrence relations of the form:</p><pre>T(n) = aT(n/b) + f(n),<br>where,<br>n = size of input<br>a = number of subproblems in the recursion<br>n/b = size of each subproblem. All subproblems are assumed <br>     to have the same size.<br>f(n) = cost of the work done outside the recursive call, <br>      which includes the cost of dividing the problem and<br>      cost of merging the solutions<br><br>Here, a ≥ 1 and b &gt; 1 are constants, and f(n) is an asymptotically positive function.</pre><p>An asymptotically positive function means that for a sufficiently large value of n, we have f(n) &gt; 0.</p><blockquote>The master theorem is used in calculating the time complexity of recurrence relations (divide and conquer algorithms) in a simple and quick way.</blockquote><h3>Master Theorem</h3><p>If a ≥ 1 and b &gt; 1 are constants and f(n) is an asymptotically positive function, then the time complexity of a recursive relation is given by</p><pre>T(n) = aT(n/b) + f(n)</pre><pre>where, T(n) has the following asymptotic bounds:</pre><pre>    1. If f(n) = O(nlogb a-ϵ), then T(n) = Θ(nlogb a).</pre><pre>    2. If f(n) = Θ(nlogb a), then T(n) = Θ(nlogb a * log n).</pre><pre>    3. If f(n) = Ω(nlogb a+ϵ), then T(n) = Θ(f(n)).</pre><pre>ϵ &gt; 0 is a constant.</pre><p>Each of the above conditions can be interpreted as:</p><ol><li>If the cost of solving the sub-problems at each level increases by a certain factor, the value of f(n) will become polynomially smaller than nlogb a. Thus, the time complexity is oppressed by the cost of the last level ie. nlogb a</li><li>If the cost of solving the sub-problem at each level is nearly equal, then the value of f(n) will be nlogb a. Thus, the time complexity will be f(n) times the total number of levels ie. nlogb a * log n</li><li>If the cost of solving the subproblems at each level decreases by a certain factor, the value of f(n) will become polynomially larger than nlogb a. Thus, the time complexity is oppressed by the cost of f(n).</li></ol><h3>Solved Example of Master Theorem</h3><pre>T(n) = 3T(n/2) + n2<br>Here,<br>a = 3<br>n/b = n/2<br>f(n) = n2</pre><pre>logb a = log2 3 ≈ 1.58 &lt; 2</pre><pre>ie. f(n) &lt; nlogb a+ϵ , where, ϵ is a constant.</pre><pre>Case 3 implies here.</pre><pre>Thus, T(n) = f(n) = Θ(n2)</pre><h3>Master Theorem Limitations</h3><p>The master theorem cannot be used if:</p><ul><li>T(n) is not monotone. eg. T(n) = sin n</li><li>f(n) is not a polynomial. eg. f(n) = 2n</li><li>a is not a constant. eg. a = 2n</li><li>a &lt; 1</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=14bb54ac3930" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Floyd-Warshall Algorithm]]></title>
            <link>https://medium.com/@mukhopadhyaypushan42/floyd-warshall-algorithm-7f09533b1878?source=rss-305d9dc4b292------2</link>
            <guid isPermaLink="false">https://medium.com/p/7f09533b1878</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[datastrucutre]]></category>
            <category><![CDATA[faang-interview-prep]]></category>
            <category><![CDATA[faang-interview]]></category>
            <dc:creator><![CDATA[Pushan Mukhopadhyay]]></dc:creator>
            <pubDate>Tue, 17 Oct 2023 13:57:38 GMT</pubDate>
            <atom:updated>2023-10-17T13:57:38.451Z</atom:updated>
            <content:encoded><![CDATA[<h3>What is a Graph Algorithm?</h3><p>Graph algorithms are a set of instructions that traverse (visits nodes of a) graph.</p><p>Some algorithms are used to find a specific node or the path between two given nodes.</p><h3>Why Graph Algorithms are Important</h3><p>Graphs are very useful data structures which can be to model various problems. These algorithms have direct applications on Social Networking sites, State Machine modeling and many more.</p><h3>Some Common Graph Algorithms</h3><p>Some of the most common graph algorithms are:</p><ul><li>Breadth First Search (BFS)</li><li>Depth First Search (DFS)</li><li>Dijkstra</li><li>Floyd-Warshall Algorithm</li></ul><p>Today I am talking about the Floyd-Warshall Algorithm.</p><p>So let’s start</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*mJFyUQdSgc2eRG0z.jpg" /></figure><h3>Floyd Warshall Algorithm</h3><p>Floyd Warshall algorithm is a great algorithm for finding shortest distance between all vertices in graph. It has a very concise algorithm and O(V³) time complexity (where V is number of vertices). It can be used with negative weights, although negative weight cycles must not be present in the graph.</p><h3>Let’s know how Floyd-Warshall Algorithm works</h3><p>Let the given graph be:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/384/0*_ROsEhDEcOGf_bhE.png" /><figcaption>Initial graph</figcaption></figure><p>Follow the steps below to find the shortest path between all the pairs of vertices.</p><ol><li>Create a matrix A0 of dimension n*n where n is the number of vertices. The row and the column are indexed as i and j respectively. i and j are the vertices of the graph.</li></ol><p>Each cell A[i][j] is filled with the distance from the ith vertex to the jth vertex. If there is no path from ith vertex to jth vertex, the cell is left as infinity.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/574/0*ACQ1gJ9J5dTLNgqS.png" /><figcaption>Fill each cell with the distance between ith and jth vertex</figcaption></figure><p>2. Now, create a matrix A1 using matrix A0. The elements in the first column and the first row are left as they are. The remaining cells are filled in the following way.</p><p>Let k be the intermediate vertex in the shortest path from source to destination. In this step, k is the first vertex. A[i][j] is filled with (A[i][k] + A[k][j]) if (A[i][j] &gt; A[i][k] + A[k][j]).</p><p>That is, if the direct distance from the source to the destination is greater than the path through the vertex k, then the cell is filled with A[i][k] + A[k][j].</p><p>In this step, k is vertex 1. We calculate the distance from source vertex to destination vertex through this vertex k.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*BT4wZjjRX1lsJyza.png" /><figcaption>Calculate the distance from the source vertex to destination vertex through this vertex k</figcaption></figure><p>For example: For A1[2, 4], the direct distance from vertex 2 to 4 is 4 and the sum of the distance from vertex 2 to 4 through vertex (ie. from vertex 2 to 1 and from vertex 1 to 4) is 7. Since 4 &lt; 7, A0[2, 4] is filled with 4.</p><p>3. Similarly, A2 is created using A1. The elements in the second column and the second row are left as they are.</p><p>In this step, k is the second vertex (i.e. vertex 2). The remaining steps are the same as in <strong>step 2</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*v6AmoTRNF2AIJRYZ.png" /><figcaption>Calculate the distance from the source vertex to destination vertex through this vertex 2</figcaption></figure><p>4. Similarly, A3 and A4 is also created.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*1J-K4Q_hCOtBdeiC.png" /><figcaption>Calculate the distance from the source vertex to destination vertex through this vertex 3</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*RpuchmDKmthmREJx.png" /><figcaption>Calculate the distance from the source vertex to destination vertex through this vertex 4</figcaption></figure><p>5. A4 gives the shortest path between each pair of vertices.</p><h3>Floyd-Warshall Algorithm</h3><pre>n = no of vertices<br>A = matrix of dimension n*n<br>for k = 1 to n<br>    for i = 1 to n<br>        for j = 1 to n<br>            Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])<br>return A</pre><p>Python Code</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cm-ceTxweEJ0i0eLe-vtqg.png" /></figure><p>Java Code</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xIjKA5OLOGuEexaXQHI8NA.png" /></figure><h3>Floyd Warshall Algorithm Complexity</h3><h3>Time Complexity</h3><p>There are three loops. Each loop has constant complexities. So, the time complexity of the Floyd-Warshall algorithm is O(n3).</p><h3>Space Complexity</h3><p>The space complexity of the Floyd-Warshall algorithm is O(n2).</p><p>I hope you understand the logic behind the Floyd Warshall Algorithm.</p><blockquote>Stay Tune</blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7f09533b1878" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solving Binary Tree Algorithms Using Recursion and Queues]]></title>
            <link>https://medium.com/@mukhopadhyaypushan42/solving-binary-tree-algorithms-using-recursion-and-queues-07ef7823dec9?source=rss-305d9dc4b292------2</link>
            <guid isPermaLink="false">https://medium.com/p/07ef7823dec9</guid>
            <category><![CDATA[recursion]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[trees]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[binary-tree]]></category>
            <dc:creator><![CDATA[Pushan Mukhopadhyay]]></dc:creator>
            <pubDate>Mon, 09 Oct 2023 06:01:55 GMT</pubDate>
            <atom:updated>2023-10-09T06:01:55.703Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/0*xBAsZm5FsssxQXon.png" /></figure><blockquote>Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value.</blockquote><p>For example, if you were given the trees</p><pre>   1            1<br> /   \        /   \<br>2     3      2     3</pre><p>the function should return true, since these trees are structurally the same and the nodes have the same value. But if you were given the trees</p><pre>   1            1<br> /   \        /   \<br>2     3      4     8</pre><p>the function should return false. Although the trees are structurally the same, they do not have the same values.</p><p>Before discussing how to approach and solve this problem, it’s valuable to talk about what binary trees are. A <strong>binary tree</strong> is a data structure containing <em>nodes</em>. The topmost node is called the <em>root</em>. Each node has a <em>value</em>, as well as a <em>right</em> reference and a <em>left</em> reference. You can learn more about binary trees <a href="https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html">here</a>.</p><p>In this problem, we want to check each node in both of the inputted binary trees and to see if their values are equal to one another, and if the structure is the same. In this post, I’ll go over two ways to approach and solve this problem with JavaScript: using recursion and using a queue.</p><h3>Approach #1: Recursion</h3><p>To solve this problem using recursion, we want to check each node in both trees. If those nodes are not equal, or if one node is null (meaning it doesn&#39;t exist) and the other one is not null, then we know the trees are not identical. Otherwise, we&#39;ll check the left nodes and right nodes, and keep going down the trees until we reach null on both trees. If the trees are null at the same point, and at no point were the node&#39;s values unequal, then we can return true.</p><h3>Coding the first approach</h3><p>To start a recursive solution, we have to consider base cases. If the nodes of both trees are null at the same point, then we can return true. If the node of one tree is null, but the other tree is not null, then we know the trees are unequal, so we can return false.</p><pre>function isSameTree1(p, q) {<br>    if (p === null &amp;&amp; q === null) return true;<br>    if (p === null || q === null) return false;<br>    //...<br>}</pre><p>If the values at the nodes are unequal, we know the trees are not identical, so we can return false. We can check the value of the nodes with .val because that was given in the Leetcode problem.</p><pre>function isSameTree1(p, q) {<br>    if (p === null &amp;&amp; q === null) return true;<br>    if (p === null || q === null) return false;<br>    if (p.val !== q.val) return false;<br>    //...<br>}</pre><p>The last element of the recursive solution is to actually make the recursive calls. We want to check both the right <strong>and</strong> the left nodes of both trees. That means we’ll want to make two recursive calls to the function, one for the nodes on the left, accessed using .left, and one for the nodes on the right, accessed using .right. We&#39;ll separate these calls with the and operator, &amp;&amp;, because the nodes have to be equal on both the right and the left for the trees to be equal.</p><pre>function isSameTree1(p, q) {<br>    if (p === null &amp;&amp; q === null) return true;<br>    if (p === null || q === null) return false;<br>    if (p.val !== q.val) return false;<br>    return isSameTree1(p.left, q.left) &amp;&amp; isSameTree(p.right, q.right);<br>}</pre><h3>Approach #2: Queues</h3><p>To solve this problem using queues, we want to create a queue for both of the inputted trees. A <strong>queue</strong> is a data structure that uses first in, first out logic: the first node to get added to the list is the first one to be removed from the list. This structure is useful when working with trees because we can add nodes in a systematic way, and check them systematically as well.</p><p>In this problem, we’ll check the first node from both queues to see if their values are different. If so, we know the trees aren’t identical, so we can return false. Otherwise, we’ll add the left and right nodes of both trees to the respective queues. If one tree has a left node, and the other one doesn’t, then we know the trees aren’t identical, so we can return false (the same is true in the case of right nodes). If we check every left and right node in both trees, they were identical every time, then we know the trees are identical.</p><h3>Coding the second approach</h3><p>We’ll start the second solution with the same base cases as above: if both tree’s roots are null, then the trees are the same, and we can return true. If one tree&#39;s root is null, but the other isn&#39;t, then the trees are different, and we can return false.</p><pre>function isSameTree2(p, q) {<br>    if (p === null &amp;&amp; q === null) return true;<br>    if (p === null || q === null) return false;</pre><pre>    //...<br>}</pre><p>We’ll want to create two queues, one for each tree. In JavaScript, we can do that by creating an array, and placing the root node in it.</p><pre>function isSameTree2(p, q) {<br>    if (p === null &amp;&amp; q === null) return true;<br>    if (p === null || q === null) return false;</pre><pre>    let queueP = [p]<br>    let queueQ = [q]</pre><pre>   //...<br>}</pre><p>Now, we’ll set up a while loop — as long as there are still values in both queues to check, we’ll keep checking the values. Inside the while loop, we’ll set up two variables — the current node in queueP that we&#39;re checking, and the current node in queueQ that we&#39;re checking. We can access these variables using .shift(), which removes the first element from an array.</p><pre>function isSameTree2(p, q) {<br>    if (p === null &amp;&amp; q === null) return true;<br>    if (p === null || q === null) return false;</pre><pre>    let queueP = [p]<br>    let queueQ = [q]</pre><pre>    while (queueP.length &amp;&amp; queueQ.length) {<br>        const currentP = queueP.shift();<br>        const currentQ = queueQ.shift();<br>        //...<br>    }<br>    //...<br>}</pre><p>If currentP and currentQ have different values, we can return false.</p><p>We want to check if there are nodes to the left of the current nodes we’re checking in both trees. If there are nodes to the left of both currentP and currentQ, then we&#39;ll push those left nodes to the respective queues. If one tree has a node to the left, but the other tree doesn&#39;t, that means their structures are not the same, so we can return false.</p><pre>function isSameTree2(p, q) {<br>    if (p === null &amp;&amp; q === null) return true;<br>    if (p === null || q === null) return false;</pre><pre>    let queueP = [p]<br>    let queueQ = [q]</pre><pre>    while (queueP.length &amp;&amp; queueQ.length) {<br>        const currentP = queueP.shift();<br>        const currentQ = queueQ.shift();<br>        if (currentP.val !== currentQ.val) return false;</pre><pre>        if (currentP.left &amp;&amp; currentQ.left) {<br>            queueP.push(currentP.left)<br>            queueQ.push(currentQ.left)<br>        } else if (currentP.left || currentQ.left) return false;</pre><pre>        //...<br>    }<br>    //...<br>}</pre><p>We can do the same for the right nodes — if both currentP and currentQ have right nodes, then we can push them to their respective queues. If one tree has a right node, and the other one does not, we can return false.</p><p>This while loop will keep checking the nodes as long as new nodes are in the queues. If every node has been added to the queues and checked in the loop, and false was never returned, then we know the trees are identical, so we can return true.</p><pre>function isSameTree2(p, q) {<br>    if (p === null &amp;&amp; q === null) return true;<br>    if (p === null || q === null) return false;</pre><pre>    let queueP = [p]<br>    let queueQ = [q]</pre><pre>    while (queueP.length &amp;&amp; queueQ.length) {<br>        const currentP = queueP.shift();<br>        const currentQ = queueQ.shift();<br>        if (currentP.val !== currentQ.val) return false;</pre><pre>        if (currentP.left &amp;&amp; currentQ.left) {<br>            queueP.push(currentP.left)<br>            queueQ.push(currentQ.left)<br>        } else if (currentP.left || currentQ.left) return false;</pre><pre>        if (currentP.right &amp;&amp; currentQ.right) {<br>            queueP.push(currentP.right)<br>            queueQ.push(currentQ.right)<br>        } else if (currentP.right || currentP.right) return false;<br>    }<br>    return true;<br>}</pre><p>Let me know in the comments if you have questions or other solutions to this problem!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=07ef7823dec9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Is competitive programming necessary to crack interviews at product-based companies?]]></title>
            <link>https://medium.com/@mukhopadhyaypushan42/is-competitive-programming-necessary-to-crack-interviews-at-product-based-companies-d71094a43569?source=rss-305d9dc4b292------2</link>
            <guid isPermaLink="false">https://medium.com/p/d71094a43569</guid>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[product-based-companies]]></category>
            <category><![CDATA[competitive-programming]]></category>
            <dc:creator><![CDATA[Pushan Mukhopadhyay]]></dc:creator>
            <pubDate>Wed, 27 Sep 2023 15:09:39 GMT</pubDate>
            <atom:updated>2023-09-27T15:09:39.888Z</atom:updated>
            <content:encoded><![CDATA[<h3>Is competitive programming necessary to crack interviews at product-based companies? Let’s end this debate….</h3><blockquote><em>Competitive programming (CP), which is a mind sport, is often compared with the problem solving, data structures and algorithms (PS/DS) interview round.</em></blockquote><blockquote><em>The purpose of this article is to clear certain misconceptions around competitive programming in the context of interview preparation.</em></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/0*014iKl6so8m67qC1.png" /></figure><h3>What happens during the interview?</h3><p>PS/DS round, also known as the coding round, is the most popular interview round for software engineering jobs at most product-based companies. The primary aim of this round is to check the coding and problem-solving abilities of the candidate. During the course of the interview, you need to map problems to basic applications of data structures and algorithms.</p><p>Having sound knowledge of data structures and algorithms, their applications and trade-offs (+practice) should be good enough to do well in a problem solving round of almost any product-based company. LeetCode, CareerCup, InterviewBit and GeeksForGeeks are popular platforms for interview preparation related to the PS/DS round.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/0*M7pPRxa0euAAmwjw" /></figure><h3>Isn’t that same as competitive programming?</h3><p>Though CP also requires the participants to have good problem-solving and coding skills, the primary objective of CP is to challenge participants to solve logical and mathematical problems. The focus is more on solving and writing efficient code for really hard problems in a short amount of time with/without applications of DS/Algo.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*2--gjgAJs3Hctq2h.png" /></figure><p>Just like any other sport, it requires you to be fit (mentally, in this case) and you can get a lot better at it with practice. CodeChef, Codeforces, TopCoder are popular platforms for competitive programming and ACM ICPC, Google CodeJam, Fb HackerCup are the most popular CP contests.</p><h3>So, is competitive programming required to do well in interviews?</h3><p>Similarly, CP may help you become a better problem solver and coder but it does not guarantee that you’ll perform well in a PS/DS round if you do not work on your data structures and algorithms fundamentals. Neither is it required for the interview if you already have decent problem-solving and coding skills and have solid understanding of DS and Algo. However, it will definitely help you in getting to the solution faster and coding it quickly if you are good at CP.</p><p>So, the short answer is: It is not essential but is definitely something that we would encourage you to try and see if you like it.</p><h4><strong>At last, I can say that CP helps coders solve algorithmic problems under time constraints to achieve the highest efficiency and accuracy which can help them to crack the hard interview round easily.</strong></h4><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d71094a43569" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Best way to solve DSA problems!!- Become a pro]]></title>
            <link>https://medium.com/@mukhopadhyaypushan42/best-way-to-solve-dsa-problems-become-a-pro-ccba897469c1?source=rss-305d9dc4b292------2</link>
            <guid isPermaLink="false">https://medium.com/p/ccba897469c1</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Pushan Mukhopadhyay]]></dc:creator>
            <pubDate>Tue, 19 Sep 2023 17:01:28 GMT</pubDate>
            <atom:updated>2023-09-19T17:01:28.726Z</atom:updated>
            <content:encoded><![CDATA[<p>Solving a DSA (Data Structures and Algorithms) problem can be pretty tough. This article should help you understand how to go about solving a DSA problem on websites like Leetcode, InterviewBit, and Geeksforgeeks.</p><p>These are the steps that you should follow:</p><blockquote>Disclaimer: It is a pretty big article. Make sure to bookmark it and reference it from time to time.</blockquote><figure><img alt="Popular Approaches to Solve Coding Problems in DSA" src="https://cdn-images-1.medium.com/proxy/1*r1ckz81ipEFmOWO8zEfUfw.png" /></figure><h3>Understand the question completely</h3><p>Look at the question and try to understand it completely. Make sure to run through the examples to verify that your understanding of the problem is correct. How to do that? The input should give the required output. You should be able to verify that.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*uzaLPxwlSwK2YmyN" /></figure><p>Write down stuff on paper if required. You need to be completely sure that you understand the problem before moving ahead.</p><h3>Get an estimate of the required complexity</h3><p>Look at the constraints and time limit. This should give you a rough idea of the expected time and space complexity. Use this step to reject the solutions that will not pass the limits. With some <a href="https://workat.tech/problem-solving/practice?tags=dsa">practice</a>, you will be able to get an estimate within seconds of glancing at the constraints and limits.</p><p>Example</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/461/0*S_QdAT2u6wqo-B_B.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/381/0*P4bJPXaJ_SWJh0Dg.png" /></figure><p>For an estimate, ~108 operations will take:</p><ul><li>1s in C/C++</li><li>2s in Java</li><li>4s in Python</li></ul><p>Most DSA problems will have the above time limits as well.</p><p>Learn how to estimate the required time complexity.</p><p>Example: For the above constraints and limits, anything worse than O(n) won’t pass.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/780/0*xr74mLsk7LIV3tQw.png" /></figure><h3>Come up with edge cases</h3><p>This is one of the most important stages. Most people miss this and get WA (wrong answers).</p><p>In most problems, you would be provided with sample input and output with which you can test your solution. These tests would most likely not contain the edge cases. Edge cases are the boundary cases that might need additional handling. Before jumping on to any solution, write down the edge cases that your solution should work on.</p><h4>What are the edge/boundary cases and how to find them?</h4><p>Boundary cases are the test cases that you can create based on the start and end boundary of the different constraint variables.</p><p>Example</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/461/0*jNisvG4-zHbpjxw5.png" /></figure><p>In the above constraints, the boundary cases are:</p><ul><li>T (No. of test cases per run): 0, 1, and 1000</li><li>N (No. of array elements per test): 1, 2, and 10000</li><li>Array element value: -100000 and 100000. Should also test on -1, 0, and 1.</li></ul><p>Create test cases (input and expected output) based on these values.</p><p>Note: Test cases mean both input and expected output.</p><p>There are different types of cases that you can create. It will be based on the use case. Learn the patterns and take care of them as you miss them on different problems.</p><p>Examples: Let’s say that the array elements can contain duplicates. Make sure to take a small test case with duplicates.</p><p>Note: It is not practical to create tests for large input sizes (T or N values) so avoid those if they are very big. Creating tests for large array element values is easy and so definitely create those.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/451/0*2AsqrB7AjZbi6nSz.png" /></figure><h3>Come up with a brute-force solution</h3><p>Come up with a solution that solves this problem correctly. It should not be the most optimal one. This solution is the one that you can come up with in less than a minute.</p><p>When you start practicing DSA, it would most likely be an exponential or polynomial solution. With sufficient <a href="https://workat.tech/problem-solving/practice?tags=dsa">practice</a>, your brute force solution would also be pretty optimal and close to the required solution.</p><p>This is generally not the solution you are going to code.</p><p>Steps:</p><ul><li>Try to come up with a correct solution as soon as possible.</li><li>Dry run your solution on the sample test cases to verify if your solution is correct.</li><li>Verify if your solution is optimal based on the time and memory limits. Do this by computing the approx number of operations based on the constraints. If it will pass then this is the required solution.</li><li>Even if it is passing, give a minute to see if you can think of a more optimal solution.</li></ul><h3>Optimize your current solution (Repeat until required optimal solution)</h3><p>Optimize your current solution if it is not going to pass based on the constraints and limits. This is one of the hardest parts of solving the problem. It gets easier with <a href="https://workat.tech/problem-solving/practice?tags=dsa">practice</a> and comfort in the required DSA.</p><p>If you’ve already computed the estimated time complexity, you can easily accept/reject the optimization ideas that come up. You would generally come up with an optimal solution after multiple iterations.</p><p>For every optimization that you come up with, compute the time and space complexity of your solution and see if it would pass. Make sure that every optimization is sending you closer to a solution that will pass the limits.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ccba897469c1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Let’s solve BCKTRACKING problems like a pro — — Part 1]]></title>
            <link>https://medium.com/@mukhopadhyaypushan42/lets-solve-bcktracking-problems-like-a-pro-part-1-ed0fb1abb897?source=rss-305d9dc4b292------2</link>
            <guid isPermaLink="false">https://medium.com/p/ed0fb1abb897</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[programming-tips]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[backtracking-algorithm]]></category>
            <category><![CDATA[recursive-backtracking]]></category>
            <dc:creator><![CDATA[Pushan Mukhopadhyay]]></dc:creator>
            <pubDate>Thu, 14 Sep 2023 17:54:16 GMT</pubDate>
            <atom:updated>2023-09-14T17:54:16.076Z</atom:updated>
            <content:encoded><![CDATA[<p>Let’s solve BCKTRACKING problems like a pro — — Part 1</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/620/0*nU3TDKcmXJjKkp5C" /></figure><p>Backtracking is a technique for solving problems by exploring all possible solutions.</p><p>Backtracking problems ask us to find combinations or permutations. These Ps &amp; Cs are then matched against certain conditions or smallest/greatest logic. Here are a couple of examples:</p><ul><li>Given an array of numbers, find all the possible combinations of numbers that add up to a given number.</li><li>Given a collection of distinct integers, return all possible permutations of them.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*HHEB5kksj5NPAqTt" /></figure><p>In this article, we will use backtracking to solve this one problem. In doing so, we will go through each step of the process in detail.</p><p>We will also look at a few important variations of these problems and how to change our solution to solve them.</p><p>In short, we can drill down backtracking to the below steps:</p><ol><li>Start from a state.</li><li>If the current state is a solution, add the current state to the result.</li><li>If not, try each of the possible moves from the current state.</li><li>Once we have tried all the possible moves, backtrack to the previous state.</li><li>Repeat the above steps until a solution is found or all possibilities have been exhausted.</li></ol><h3>Problem 1: Combinations</h3><p>Let’s solve the below problem:</p><p>_Given a list of distinct positive numbers, find all combinations that add up to a given number.</p><p>Input: [1, 2, 3, 4], target = 5 Output: [[2, 3], [1, 4]]_</p><p>Let’s use the backtracking technique to solve this problem.</p><p>Disclaimer: There are many ways to solve this problem. I have chosen a way that will be easy to explain. I have left out any clever tricks to keep the code simple. The programming examples are in Java but do not use any special data structures.</p><h3>Initial State</h3><p>The initial state is an empty list. We are going to start from this state and try to add numbers to it.</p><p>We will keep track of:</p><ol><li>The current state or list of numbers used.</li><li>The sum of the numbers in the list.</li></ol><pre>public List&lt;List&lt;Integer&gt;&gt; combinationSum(int[] nums, int target) {<br>    // will store the final result<br>    List&lt;List&lt;Integer&gt;&gt; res = new ArrayList&lt;&gt;();</pre><pre>    // keeps track of the current state<br>    List&lt;Integer&gt; current = new ArrayList&lt;&gt;();</pre><pre>    // call the helper function which does the processing<br>    // first 0 is the sum of the numbers in the current state<br>    // second 0 is the index to start from<br>    backtrack(nums, target, 0, 0, current, res);<br>    return res;<br>}</pre><h3>Check if the current state is a solution</h3><p>We need to check if the current state is a solution. To do so, we need to check if the sum of the numbers in the current state is equal to the target.</p><p>If yes, we will add the current state to the final result.</p><pre>void backtrack(int[] nums, int target, int sum, int index, List&lt;Integer&gt; current, List&lt;List&lt;Integer&gt;&gt; res) {<br>    // if the sum of the numbers in the current state is equal to the target,<br>    // then we have found a solution<br>    if (target == sum) {<br>        // copy the content of the current state to a new list and save to result<br>        res.add(new ArrayList&lt;&gt;(current));<br>        return;<br>    } else if(sum &gt; target) {<br>        // short circuit, if the sum of the numbers in the current state is greater than the target,<br>        return;<br>    }</pre><pre>    // to be continued...<br>}</pre><h3>Try each of the possible moves and backtrack</h3><p>If the current state is not a solution, we need to try each of the possible moves.</p><p>The possible moves are all the numbers in the nums array that comes on or after the index.</p><p>We can divide this into 3 steps:</p><ol><li>Add a number to the current list to get to the next state.</li><li>Call the backtrack function to check if the next state is a solution. Update the index and sum being sent to the backtrack function.</li><li>Remove the number from the current list to get back to the previous state. The next iteration will try the next number.</li></ol><pre>void backtrack(int[] nums, int target, int sum, int index, List&lt;Integer&gt; current, List&lt;List&lt;Integer&gt;&gt; res) {<br>    // checking for solution - omitted</pre><pre>    for (int i = index; i &lt; nums.length; i++) {<br>        // add the current number to the current state<br>        current.add(nums[i]);</pre><pre>        // call the helper function to try the next state - Current sum is updated and index is increased to the next number<br>        backtrack(nums, target, sum + nums[i], i + 1, current, res);</pre><pre>        // remove the current number from the current state<br>        current.remove(current.size() - 1);<br>    }<br>}</pre><h3>Variation 1: Numbers are not distinct</h3><p>If we ran the same solution, but with the numbers not being distinct, we would get duplicate results. For e.g. [1, 2, 2, 3, 4] will return [[1, 2, 2], [1,4], [2, 3], [2, 3]]</p><h4>Solution 1: Set to Store Result</h4><p>The simplest way to solve this problem is to use a Set to keep track of the final result and convert the set to a list at the end. Although this will lead to a correct solution, this does lead to some unnecessary work being done. Duplicate results are still being calculated even if not included in the result.</p><pre>public List&lt;List&lt;Integer&gt;&gt; combinationSum(int[] nums, int target) {<br>    // will store the temporary result<br>    Set&lt;List&lt;Integer&gt;&gt; res = new HashSet&lt;&gt;();</pre><pre>    List&lt;Integer&gt; current = new ArrayList&lt;&gt;();<br>    backtrack(nums, target, 0, 0, current, res);</pre><pre>    // convert the set to a list<br>    return new ArrayList&lt;&gt;(res);<br>}</pre><h4>Solution 2: Avoid Duplicate Moves</h4><p>A better way is to exclude duplicate moves while forming the next state.</p><p>Suppose our current state is [1] When we loop through the remaining numbers, we can get the below possible states: [1, 2], [1, 2], [1, 3], [1, 4]</p><p>To avoid the duplicate move, all we need to do is to check if a number is being processed twice.</p><p>We will put the processed numbers in a Set and if a number is already in the set, we can skip it.</p><pre>void backtrack(int[] nums, int target, int sum, int index, List&lt;Integer&gt; current, Set&lt;List&lt;Integer&gt;&gt; res) {<br>    // checking for solution - omitted</pre><pre>    Set&lt;Integer&gt; set = new HashSet&lt;&gt;();<br>    for (int i = index; i &lt; nums.length; i++) {<br>        // if the current number is already in the set, skip it<br>        if (set.contains(nums[i])) {<br>            continue;<br>        }</pre><pre>        //processing - call and backtrack - omitted</pre><pre>        // add the current number to the set<br>        set.add(nums[i]);<br>    }<br>}</pre><p>We can further remove the set if the order of the result is not important.</p><p>The steps for this are:</p><ol><li>Sort the initial array so that all duplicates come together.</li><li>Instead of using a set, compare numbers to the previous number and skip if it’s the same.</li></ol><p>The below code can replace the Set logic once the array <em>nums</em> is sorted.</p><pre>void backtrack(int[] nums, int target, int sum, int index, List&lt;Integer&gt; current, List&lt;List&lt;Integer&gt;&gt; res) {<br>    // checking for solution - omitted<br>    for (int i = index; i &lt; nums.length; i++) {<br>        // if the current number is already in the set, skip it<br>        if (i &gt; index &amp;&amp; nums[i] == nums[i - 1]) {<br>            continue;<br>        }<br>        //processing - call and backtrack - omitted<br>    }<br>}</pre><h3>Variation 2: Numbers Can Be Used any Number of Times</h3><p>If we could use each number any number of times, the result changes. For e.g. For a target sum of 5, [1,2,3,4] will return [1,1,1,1,1], [1,1,1,2], [1,1,3], [1,2,2], [1,4], [2,3]</p><p>This leads to a very small change in our recursive call. Since the same number can be used again in the solution, we will not increment the index while calling the recursive function.</p><pre>void backtrack(int[] nums, int target, int sum, int index, List&lt;Integer&gt; current, List&lt;List&lt;Integer&gt;&gt; res) {<br>    // checking for solution - omitted</pre><pre>    for (int i = index; i &lt; nums.length; i++) {<br>        current.add(nums[i]);</pre><pre>        // sum is updated but index is not incremented<br>        backtrack(nums, target, sum + nums[i], i, current, res);</pre><pre>        current.remove(current.size() - 1);<br>    }<br>}</pre><h3>Time Complexity</h3><p>The theoretical Time complexity of each of these backtracking algorithms is O(N!) where N is the number of elements in the input array.</p><p>This can be calculated by the following intuition:</p><ol><li>At every step, we have N choices to choose from.</li><li>After making all choices, we have to make N-1 choices for each of them.</li><li>And so on.</li></ol><p>Number of steps = Nx(N-1)x(N-2)x…x1 = N!</p><p>This does not mean all backtracking algorithms are O(N!). It all depends on the number of choices we have at each step.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ed0fb1abb897" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>