## Count of binary strings without consecutive 1’s

Given a positive integer N, find the count of distinct binary strings of length N that have no consecutive 1’s. For example,

```Input:
N = 2
Output:
3.
Explanation:
There are 3 possible strings: 00, 01, 10N=3There are 5 possible strings: 000, 001, 010, 100,101
```

## Thought process to find binary strings with consecutive 1s

This problem is an easier variation of digit DP problem. Since these are binary strings for every position in the string there are just two choices: 0 and 1. To form a string of length N, at any position –

1. We can choose 0 and then for the next position we again have two choices.
2. We can choose 1 but then for the next position we cannot choose 1 as we don’t want consecutive 1’s in the string. So once we choose 1, we are also setting next position to 0.

So in case (a), we set 0 at current position and the problem then reduces to count the number of strings having length N-1 with the given condition.

And in case (b), we set 1 at current position and 0 at next position, hence the problem reduces to count the number of strings having length N-2 with the given condition.

With this we can write

Count(n) = Count(n-1) + Count(n-2)

Does this formula ring a bell? Yes, it’s the same one that is is used to find Fibonacci numbers.

As Count(1) = 2, Count(2) = 3, Count(3) = 5, ……
and Fib(1) = 1,  Fib(2) = 1, Fib(3) = 2, Fib(3) = 3, Fib(4) = 5, ……

Hence we can observe that-
Count(n) = Fib(n+2)

Using the explanation for DP approach and the implementation in Find Nth Fibonacci number problem:

```#include <iostream>
#include <vector>
using namespace std;

long long int fib(int N)
{
vector<long long int> DPVec(N+1, 0);
DPVec = 1; DPVec = 1;
for (int i=3; i<=N; ++i)
{
DPVec[i] = DPVec[i-1] + DPVec[i-2];
}
return DPVec[N];
}

long long int Cnt_strings(int N)
{
return fib(N+2);
}

int main()
{
int n = 3;
cout<<Cnt_strings(n)<<endl;
return 0;
}
```
```public class Count_Strings
{
static int fib(int N)
{
int DPArr[] = new int[N+1];
DPArr = 1; DPArr = 1;
for (int i=3; i&lt;=N; ++i)
{
DPArr[i] = DPArr[i-1] + DPArr[i-2];
}
return DPArr[N];
}

static int Cnt_strings(int N)
{
return fib(N+2);
}

public static void main (String[] args)
{
int n = 4;
int num_strings = Cnt_strings(n);
System.out.println(num_strings);
}
}
```
The time complexity of the implementation is O(n) and space complexity is also O(n)
Posted on Leave a comment on Count of binary strings without consecutive 1’s

## Maximum Path Sum in Binary Tree

Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along with the parent-child connections. The path must contain at least one node and does not need to go through the root. For example

```Example 1:

Input: [1,2,3]

1
/ \
2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

Output: 42
```

If you want to watch the video, you can check here:

## Maximum Path Sum: thought process

We already have solved quite a few problems on path sum in binary trees like finding the sum of all paths, find a path with a given sum, find sum with maximum sum. Difference between problems we saw before and this one is that in this question the path may not pass through the root. The path here is not defined between root and leaf node, but any two nodes. In example 2, the maximum path sum is 15->20->7, which is the path between node 15 and node 7.

A lot of things are going on here, let’s decouple some things. First of all, we have to keep a global maximum. Second, the root may be part of the maximum path or it may not be.
The first problem is simple to solve, we will keep a global variable (I know, we can change it with an array param). For the second problem, if we do not include node in the path, that means we will not be including any node in the subtree rooted at this node, because a path has to be continuous and we cannot skip the node. Now, we have to decide when to include the node in the path and when not to.

At each node, we are returning the maximum sum we can get from the subtree under this node.

Each node actually does two things: When processing the final result maxValue, the node is treated as the highest point of a path. When calculating its return value, it is only part of a path (left or right part), and this return value will be used to calculate the path sum of other paths with some other nodes(above the current one) as their highest point.

If the maximum sum which can be achieved from the tree under the node is negative, there is no point including any path which crosses this node as it will lead to the smaller global sum, hence we mimic that making sum received from such a node as zero.
In example 2, adding -10 to the path sum (9) of the left subtree makes it negative, there is no point connecting the left subtree path (09 + -10) to the right subtree path as it will lead to a smaller sum.

At every node, we update the maximum sum we can get at that node, by adding left path sum, right path sum, and root value. We check if that is greater than known max, we update the global max. After updating the global max, we have to return the maximum sum we can achieve at the node, by getting the max sum of left subtree and right subtree and adding root.value to it. To the upper layer(after return statement), we cannot choose both left and right brunches, so we need to select the larger one, so we use max(left, right) + node.val to prune the lower brunch.

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return res;
}
private int dfs(TreeNode node) {

if(node == null) return 0;

//Get maximum sum on the left subtree
int l = Math.max(0,dfs(node.left));
//Get maximum sum on right subtree,
// if negative, make it zero
int r = Math.max(0,dfs(node.right));

//Update the global value.
res = Math.max(l + r + node.val, res);

//Return max sum of the path including this node.
return Math.max(l, r) + node.val;
}
}
```

As we traverse each node of the tree, the overall complexity of the implementation is O(n).

Posted on Categories AlgorithmsLeave a comment on Maximum Path Sum in Binary Tree

## Spiral traversal of a matrix

Given a 2d matrix of dimension n*m, the task is to print the matrix in spiral order. (To understand what is spiral order please refer to the diagram) For example:

```Input:
3 3
1 2 3
4 5 6
7 8 9

Output:
1 2 3 6 9 8 7 4 5
```

Explanation: The below diagram clearly shows the order of printing to be followed. ## Spiral traversal of a matrix thought Process

1. The number of elements to be printed is n*m. We will maintain a count variable to keep track of the number of elements printed till now.

2. There are four directions in which we need to print the elements as shown below. The numbering indicates the order of printing. 3. For each direction, we need start and end to print the elements. Let’s maintain four variables, row, col, rowe, cole.

```row = row starting index
col = column starting index
rowe = row ending index
cole = col ending index
```

Let, row = 0, col = 0, rowe = 2, cole = 2, After handling any row or column, we need to update the variables.

4. To handle rows like this, We will print elements from col to cole i.e, [0,2] with the row being fixed. After printing each row, we will update the row to row + 1.
Now, row = 1
5. To handle column like this, We will print elements from row to rowe i.e, [1,2] with cole being fixed. After printing each column, we will update the cole to cole – 1. Now, cole = 1

6. To handle rows like this, We will print elements from cole to col i.e, [1,0] with the row being fixed. After printing each row, we will update the rowe to rowe – 1. Now, rowe = 1

7. To handle columns like this, We will print elements from row to rowe i.e, [1,1] with col being fixed. After printing each column, we will update the col to col + 1.
Now, col = 1

Points 4,5,6,7 explains four operations. These four operations need to be performed in a loop until the number of elements printed reaches n*m. As soon as printed elements reach n*m, break out of the loop.

Any corner cases or where you can make mistakes? Yes. Take care of the cases where the number of rows is 0 and check whether the number of printed elements reaches n*m or not in every loop.

The code is given below:

```public class Solution {

public static void spiralPrint(int a[][]){

int n = a.length;

if(n == 0)
return;

int m = a.length;

int count = n*m;
int num = 0;

int row = 0, col = 0;
int rowe = n-1, cole = m-1;

while(num &lt; count)
{
// step 4
for(int i = col; i <= cole && num < count; i++)
{
System.out.print(a[row][i] + " ");
num++;
}
row++;
// step 5
for(int i = row; i <= rose && num = col
&& num = row && num < count; i--)
{
System.out.print(a[i][col] + " ");
num++;
}
col++;
}

}
}

```

The time complexity of the implementation is O(n*m) as we are doing constant work on every index whereas space complexity is O(1) as no extra space is used.

This article is contributed by Mukul, if you also contribute to Algorithms and Me, please check out our publisher’s program.

Posted on Categories Algorithms, Microsoft Interview QuestionsTags Leave a comment on Spiral traversal of a matrix

## The DS/Algorithm Interview Script

Disclaimer: This post deals with the traditional “coding” interview where the focus is on solving one or more coding problems. I have interviewed in a double-digit number of companies from India, the US, and Europe and this post is a culmination of those experiences. This is the stable, generic approach I use in my interviews.

Interviews have certain aspects of randomness due to factors like the company you’re interviewing for, the interviewer, job role etc. Despite this, there are certain steps you can take which will help the interviewer judge the clarity of your thought process, thoroughness while solving problems, and overall problem solving ability. While the two scripts below try to provide a general path on approaching problems during an interview, remember that you have to improvise depending on how the interview is going, and the best way to achieve good results is to be yourself during the interview. A calm mindset while approaching the interview helps significantly, and there is no better way to establish a rapport with the interviewer than to be sincere :).

Another important aspect of the interviewing that I have noticed a lack of, is that most people try to approach an interview as a showcase-my-abilities experience, or a me-vs-the-company battle. It is not. An interview is a journey you and the interviewer take together where you solve a problem and get to know each other better(not just your abilities, but also who you are). Don’t be afraid to ask questions or speak your mind.

As an interviewee, you do not always play at the backhand. An example of this is concepts which I’m not completely sure about. I’ll often let the interviewer know that I’ll be looking it up, or straight up Googling it. I follow it up by explaining exactly what it was that I looked up and how that concept helps with my solution. Actively guiding the interview showcases that you can take charge when needed and bring the problem to its logical conclusion. After all, you are interviewing the company and judging it as much as they are you. Don’t come on too strong though ;).

## Solving a problem

Remember: Think out loud! (more tips on this at the end)

Solving a particular coding problem usually involves the following steps: My question solving script

I discuss the flow of the interview and each step in detail below:

• Question – This is the question that is provided by the interviewer. You need to read it in thorough detail. Read it multiple times if necessary. There are multiple ways to approach it at this point. If you have a general idea of how to solve the problem, good for you. If not, try to identify if the problem is a mutation of a known, classical problem(e.g. searching in a graph), or some combination of those. If this doesn’t work either, try to come up with the simplest way you can solve the problem. Don’t think about complexities and optimizations at this point.

• Discussion – Your first step should be telling the interviewer exactly what you’re thinking and how you are working on refining the idea. It is important that you talk to the interviewer because they will help guide you in the right direction and correct any obvious mistakes you might be making. You might also have missed some details previously, and the interviewer can point those out to you. You know that feeling when someone you’re talking to is obviously wrong and you can’t help it but try and correct them? Yeah, that’s what we’re going for.
ASK QUESTIONS. I cannot stress this enough. Interviewers are often banking on the interviewee asking clarification questions and might leave out a detail or two to see if you understand the problem enough to notice it. They might have made a mistake and won’t know till you ask them. Any assumptions you make should be clarified. And the most important thing discussing the problem with the interviewer does at this point, is open up two-way communication and build a rapport between you two from the get go. Both of you are more comfortable and will have a better overall interview experience. Win-win!

• Test Case check – At this point in the interview when I understand the question really well, I will often look at the test cases to identify if the idea I’m thinking of works with the given test cases. Are there any obvious gotchas that they show me? Can I come up with a test case where my solution is still in a grey area? Can I ask the interviewer about this grey area and get more test cases? And as always, think out loud.

• Discuss Brute-force – Unless I am sure I have an efficient solution completely figured out in my head, I always, always, always, discuss the brute-force solution with the interviewer. The brute-force solution is usually easy to implement, gets working (pseudo?)code written down which the interviewer can use to score you/come back to later, and has easier time and space complexity discussions. Usually when discussing the brute-force solution, basic optimizations become obvious, and it gives us future paths which are useful in coming up with an efficient solution.
My process with this is to explain all the steps in my algorithm to the interviewer as a gist, since we will be going into more detail while writing actual code.

Edit: Divye has correctly pointed out that over time, as you practice giving interviews, you develop an intuition of developing the efficient solution in the first go. “But if a preconceived notion of needing to start out with brute force exists, often you lose out on that spark.”, as he wisely put it. I have noticed that I tend to rely more on my instinct, now that I know that I will follow a process and only need to worry about coming up with a solution. Experience helps with this too, I’m sure. Others have pointed out that an efficient solution can strike you midway at any step, and depending on the time remaining, you should judge whether to switch to that solution. Sound advice. But you always have this process to fall back on in case anything starts going awry ;).
Another good point brought up is thinking about the competition. Somebody out there is going to come up with an optimal solution no matter what. It’s a question of showcasing technical ability vs superiority. I am fine with the former, but you do you.

• Implement Brute-force – There is a decision to be made here: Should you implement the brute-force solution, or is it better to discuss and implement a more efficient solution? The more efficient solution will score you more points in that vertical, but if you are unable to come up with a complete efficient solution, it is better to have complete brute-force code. Completeness scores high as a measure because it showcases that you could correctly assess the constraints, including your abilities and the problem, and come up with a solution that works. Taking this decision involves quick judgment on your abilities and how deeply you understand the problem. I tend to not give myself the benefit of doubt and implement the brute-force if I cannot map out an efficient solution in my head yet. Leave a few minutes if the time for the interview is ending to complete the final discussions.
There are some general coding tips at the end of this section.

• Discuss Efficient solution – Wooo! Look at you discussing an efficient solution! You can get here either before implementing a brute-force solution, or after. In either case, you should be able to talk out loud how you came up with the approach or optimizations (if you knew it before, why didn’t you just implement it before?). Depending on the time remaining, and whether I have implemented a brute-force solution already, I will go into significant detail explaining this solution if I feel I will not be able to implement it completely, or less detail otherwise.

• Implement Efficient solution – If you’re here, you’re in a good spot in the interview :). This is you putting your best foot/solution forward, so you can confidently go forward. Again, leave some time at the end for further discussions. Coding tips are at the end.

• Dry run cases – Use the given test cases to verbally, STEP-BY-STEP walk through each line of your code and how it will execute. You don’t need to write down the intermediate values if you’re confident, but in some complex cases, I prefer writing those variable values down. This catches basic errors in your code, makes it easier for the interviewer to understand exactly what you’ve done, and shows the interviewer that you care about testing your code.

• Edge cases – The next step is stress-testing your code. Try out null values. Check for overflows. Any complex logic in your code? Make an edge case for that. Try out as many crazy inputs in your code as you can. DRY RUN THEM VERBALLY so your interviewer knows what you’re trying out. Increases your confidence in your code, and shows the interviewer how well you understand the system and underlying constraints.

• Time & Space complexity – I prefer having this discussion before discussing scalability, concurrency etc. so that we have bolted down this problem as solved and completed our discussion. Everything else is a perk. I usually approach time and space complexity in a bottom-up fashion, starting from the most basic operation and going up the tree. This approach verifies my values, and shows that I understand the process of calculating the complexity. I usually write this down at the end of my code in comments.

• Further discussion – Depending on the company, the time remaining and how the interview has gone, I will often discuss further with the interviewer, for e.g., how do I implement such an algorithm concurrently? How would I scale this approach to X users? How would I manage memory in case this grows too large?

### Coding tips

• Please use good variable names! var1 is useless when you come back to the code 2 months later, and to understand what the variable does. activeUserCounter is a much better descriptor. The typing speed argument should not matter (auto-complete, copy-paste), and the benefits are absolutely worth it.

• Follow a standard coding style. I don’t care what you use unless you’re doing something unheard of, but follow a consistent pattern. This is often language and convention dependent.

• Don’t be afraid of classes/functions etc. Sure, you might feel that they add extra time not spent on writing logic, but if it simplifies understanding of your code, it will often be worth it. Not just for the interviewer, if you structure your code well, you have less cognitive load when writing other parts of your code.

## The Technical Interview Script

A technical interview is not just problem-solving, though that is primary. The basic script looks like: A simple technical interview flow
• YOU NEED AN ELEVATOR PITCH. Don’t worry, it doesn’t make you one of those MBA-types. And you will invariably be asked to describe yourself at the beginning of the interview. The elevator pitch for an engineer is usually a 2 minute monologue on your work, or your journey, interspersed with some technical details and some real-life impact. You don’t need to explain everything. You shouldn’t say too little either. Remember the skirt analogy. If you don’t have one, make one and then tell it to as many people as you can and ask them what they think. In a few iterations, you should have something ready. Also, practice it till you can speak it confidently, since this is the first impression you’re going to leave on the interviewer.

• N Questions – Depending on the company, you will be expected to solve some questions. We’ve already discussed the question approach beforehand.

• Your questions – Depending on the time remaining, you can ask all the questions that might be plaguing you about the company. Don’t hesitate. Don’t be an idiot, but if you have a genuine doubt, no matter what it is, you shouldn’t hesitate. I usually ask about the creative freedom and ownership responsibilities because I am always curious about those, but your mileage may vary. Depending on how my interview went, I usually ask the interviewer if I performed well in all verticals they were judging me on.

• Call me maybe? – Well, that’s it. You’re done with the interview and now the only thing to do it wait. I’m not good at that, so best of luck! 🙂

### Practicing

These are my practices(?) for practicing interviews:

• Nothing replaces the real thing. Give mock interviews. I’m lucky enough to have friends who are already interviewers, and know how to create an atmosphere of a real interview. We try to not be friends during that time and recreate an interview as much as possible. Finding people who can interview you is a difficult personal journey, but I would spend significant time finding these people so that I can get working on this part of the process.
I started interviewing after I had revised all my concepts, and solved a large number of problems of all types on an online judge(I used Leetcode). Thus, I learnt to jump from question to solution in my head, detracting from training in the process of solving a question. In hindsight, that is the wrong approach, and I should have started right after I had revised most of my theory concepts and was practicing problems. A lot of steps in the question script came about as a result of feedback from my mock interviews. I had to consciously change how I approached solving problems while interviewing, and that is definitely the hard way. Why not just train yourself to think the interview way when practicing from the first time?

• If (and this is not a political statement) in the years post 2020, paper-pen and whiteboard interviews are in fashion again, you need to practice solving problems on the medium. You can still pull off a decently similar experience using video calls and paper-pen, or a whiteboard, I imagine. Most of my post quarantine interviews have been completely over telephone or video, though.

## Thinking out loud

Ok, I know this is the bane of coding rounds in interview. If you say things out loud, you’re gonna think slower and might not be able to finish, but if you don’t, the interview is just a black hole where sometimes you might discuss something, but there is a major communication gap between you two. It is hard in the beginning, but if you remember to do a few simple things, you should be doing this in no time!

• Practice by teaching someone in extreme detail. It doesn’t matter what algorithm or concept you teach, this will help you in being able to talk about detailed aspects of the work using simple language and analogous concepts which will help you when you’re trying to explain what you’re thinking of on the fly. I notice that I clear the idea out in my head the fastest if I explain a concept to a friend from a widely different field, e.g. binary to decimal conversion and vice versa to my doctor friend.

• You don’t have to say everythingKnowing what to say is an art form in itself, but a simple tradeoff I make is if I know I’m not going to be able to talk while performing a task, e.g. dry-running on a case, I will prefix all my silent computations in my head by explaining what I will be doing in my head, e.g. “I’m about to try and prove if collinearity exists in this case, so I might fall silent, but I’ll try to keep you updated on what I’m thinking”. In any case, every few minutes I will let them know where I am.

• You don’t have to be completely coherent – They know you’re thinking on the fly and might not have things figured out in your head. You might talk about unrelated topics, concepts which you’re skimming to see if they fit the problem, or weird ideas which pop up in your head. They don’t have to be coherent together. But you should speak in complete sentences as much as possible :p. And once you’ve ideated and have an approach ready, you should be fairly coherent then.

• Ask them questions – You don’t have to be the only one talking. I often ask validation questions when talking, e.g. “Does that sound good?”. The responses often let me know how confidently the interviewer understands what I’m talking about, and I can course correct if I make any mistakes. These questions also buy you some time while making the interviewer pay active attention to you.

That does it for this post. Phew. That was a long one, wasn’t it? This is a very subjective post, and let me know any comments/suggestions/improvements.

Authored by Khushman, with feedback from too many people to list. I’m grateful for my smart friends. The rest of you, you I know I love y’all :).

Posted on Categories Algorithms, Data Structures, Interview ExperiencesLeave a comment on The DS/Algorithm Interview Script

## Bit Manipulations – Part 1

When it comes to problem-solving during interview preparations or competitive programming there are many instances where we encounter errors like Time Limit Exceeds (TLE). These errors are mostly due to the fact that our solution does not run in stipulated time limit and it crosses the allotted time limit.

To counter this problem, there are many algorithms available and Bit Manipulation is one of them. Bit manipulations are fast and can be used in optimizing time complexity. You would be thinking what is the use of Bit manipulation if we have other algorithms/ways to solve the problems.

Consider a problem- XOR of Sum of all possible pairs of an array

A naive approach is to run two loops consider each pair and then find the sum of each pair and then calculate XOR of all the sums.

In this case, time complexity- O(n2)

An optimized approach is based on the XOR operation. We know that the XOR of the two same numbers is Zero. So pairs like (a,b), (b, a), (a, c), (c, a) will have the same sum and hence their XOR will be Zero. so we need to consider pairs like (a, a), (b, b), (c, c) and hence XOR of the sum of pairs will be XOR of all elements of the array multiplied by 2.

In this case, time complexity is O(n)

We will discuss the above problem in detail in upcoming article.

## Bit manipulation in detail

Now let us understand bit manipulations in detail.

Bit Manipulations is nothing but an act of applying logical operations on bits to achieve the desired result.

Since implementing bit manipulation involves logical operations, so let’s start our discussion with logical operators and their respective operations.

Logical Operations

Logical operations are any set of operations which involves manipulating bits using some operators and such operator are known as Logical Bitwise Operators.

So far we have basic understanding of bit-wise operators and respective operations. Now we will be diving deep into bit manipulation concepts.

## Important bit manipulation tricks for problem solving

1. Left Shift

In left shift each bit is being shifted by k bit(s) towards left and consequently most significant bit (MSB) is discarded. In this example – 00010111 = 23 00101110 = 46 It implies that 23<<1 = 46
1. 2 << 1 = 4
2. 2 << 2 = 8
3. 2 << 3 = 16

Did you observed some pattern in above examples?

Yes, here’s a trick. Observe carefully and you will get that 2 << 1 = 2 * power(2, 1) , 2 << 2 = 2 * power(2, 2) and so on.

If there is a number N and we have to perform left shift by i bits, then N = N * power(2, i)

2. Right Shift

In right shift each bit is being shifted by k bit(s) towards right and consequently least significant bit (LSB) is discarded. In this example –00010111 = 2300101110 = 11It implies that 23>>1 = 11

Let’s have a look at some more examples

1. 8>> 1 = 4
2. 8 >> 2 = 2
3. 8 >> 3 = 1

Did you observed some pattern in above examples?

Yes, here’s a trick. Observe carefully and you will get that 8 >> 1 = 2 / (power(2, 1)) , 8 >> 2 = 8 / (power(2, 2)) and so on.

Conclusion : If there is a number N and we have to perform right shift by i bits, then N = N / ( power(2, i)

3. Swapping two numbers

Suppose a=2 and b=3, then we need a=3 and b=2, so swapping will be done as-

```def swapping(a,b):
a=a^b
b=a^b
a=a^b
print(a,b)
def main():
a=int(input())
b=int(input())
swapping(a,b)
if __name__=="__main__":
main()
```

4. To check whether number is even or ODD

Let’s observe some even and odd numbers and their respective binary representations-

```2 = 0010
3 = 0011
4 = 1000
9 = 1001
10 = 1010
```

Upon carefully observing the binary representations of above numbers you will find that if a number is even then LSB is 0 else LSB is 1.

Now observe one more thing-

```2 & 1 => 0010 & 0011 = 0000
3 & 1 => 0011 & 0001 = 0001
9 & 1 => 1001 & 0001 = 0001
4 & 1 => 0100 & 0001 = 0000
```
Bitwise AND of N with 1 is 0 for even numbers and is 1 for odd numbers.
```def oddeven(N):
if(N&amp;1==0):
print("EVEN")
else:
print("ODD")
def main():
N=int(input())
oddeven(N)
if __name__=="__main__":
main()
```

5. How to set a bit in a number N

If we want to set a bit at kth position then-

• Left shift 1 k times (let p=1<<k)
• Find bitwise OR of N with p i.e. answer=N|p

Consider and example-

N=8 (1000) suppose we want to set 2nd bit means k=2 since 1 = 0001 (in binary) Therefore, p=1<<k

p=0100 (in binary)

Hence, N | p = 1000 | 0100 = 1100 (equivalent to 35 in decimal)

```def setKthBit(N,k):
p=1&lt;&lt;k
answer=N|p
return answer
def main():
N,k=map(int,input().split())
print(setKthBit(N,k))
if __name__=="__main__":
main()
```

6. How to unset a bit in a number N

If we want to unset a bit at kth position then-

• Left shift 1 k times (Let p=1<<k)
• Negate p => ~p
• Find bitwise AND of N with ~p , it will unset the required bit.

Suppose N=51 and k=4 N = 110011 then, p = 1 << 4 = 010000 So, ~p = 101111

Therefore N & ~p = 100011 (equivalent to 35 in decimal)

```def setKthBit(N,k):
p=1&lt;&lt;k
answer=N &amp; ~p
return answer
def main():
N,k=map(int,input().split())
print(setKthBit(N,k))
if __name__=="__main__":
main()
```

So far we have learned some basic but useful concepts in bit manipulation.

In the Second Part of Bit Manipulation series I will be covering some important concepts with tips and tricks like-
• Check if kth bit is set.
• Count Number of set bits.
• Toggle a bit at kth position.
• Check if a number is divisible by 3
• Swap all odd and even bits
• Binary to gray code conversion
This article is contributed by Md Taslim Ansari
Posted on Categories Algorithms, Bitwise operationsLeave a comment on Bit Manipulations – Part 1

## Optimal Binary Search Trees

BSTs are used to organize a set of search keys for fast access: the tree maintains the keys in-order so that comparison with the query at any node either results in a match, or directs us to continue the search in left or right sub-tree.

For this problem we are given a set of search keys (0, 1, … n) along with the search frequency count (f0, f1, …. fn) of each key. The set of keys is sorted. A BST can be constructed from such a set of keys, so that keys can be searched quickly but there’s a cost associated with the search operation on BST. Searching cost for a key/node in the BST is defined as – level of that key/node multiplied by its frequency. Level of root node is 1. Total searching cost of the BST is the sum of searching cost of all the keys/nodes in the BST. Given a set of keys the problem is to arrange the keys in a BST that minimizes the total searching cost.

For example:
Keys: {0 ,1} and Freq: {10, 20}
Possible BSTs created from this set of keys are:

```1) Total cost of BST = (level of key0 * freq of key0) +
(level of key1 * freq of key1)
= (1 * 10) + (2 * 20)
= 50
2) Total cost of BST = (level of key1 * freq of key1) +
(level of key0 * freq of key0)
= (1 * 20) + (2 * 10)
= 40 ```

Hence, the minimum total searching cost for given set of keys is 40.

## Thought Process:

As per definition of searching cost for a key in the BST – (level of key (L) * freq of key (F)), here we can observe that starting from level ‘1’ till level ‘L’ at each level the key contributes ‘F’ to the total cost and that’s why its searching cost is (L * F).

In order to minimize the total search cost, a simple Greedy approach comes to mind where we try to keep keys with higher frequency at the top of the tree like we choose the key with highest frequency as root, then from the keys on the left of it we again choose a key with highest frequency and make it the left child of root and similarly we choose the right child of the root from the keys on the right and build a BST.

But will this approach build a BST that give minimum total search cost? To prove a Greedy approach works, we have to give a proof. But to prove a Greedy approach fails, we just have to give an example where it doesn’t work.

Let’s consider this example:

Using the Greedy approach discussed above let’s build a BST and calculate its total cost:
Key ‘4’ has highest frequency: 25, so it will be the root. Keys {0,…,3} will be used to build the left sub-tree and keys {5, 6} will be used to build the right sub-tree.
Among keys {0,…,3}, key ‘0’ has the highest frequency, hence it will be the left child of the root.
Among keys {5, 6}, key ‘6’ has the highest frequency, hence it will be the right child of the root.
We keep doing this all the remaining keys and the final BST would look like this:

```If Level of Key(k) is Lk and Frequency of Key(k) is Fk, then -

Total cost of Greedy BST = (L4 * F4)+(L0 * F0)+(L6 * F6)+
(L2 * F2)+(L5 * F5)+(L1 * F1)+
(L3 * F3)
= (1 * 25)+(2 * 22)+(2 * 8) +
(3 * 20)+(3 * 2) +(4 * 18)+
(4 * 5)
= 243```

But is there any other possible BST that has lower total searching cost?
Let’s consider this BST:

```Total cost of this BST = (1 * 20) + (2 * 22) + (2 * 25) +
(3 * 18) + (3 * 5) + (3 * 8) +
(4 * 2)
= 215```

This BST has lower total cost (215) than the BST created using Greedy approach (243). Hence the Greedy approach fails to solve this problem. But then how do we find the optimal BST?

## Solution:

Let’s consider a given set of keys {Ki, … , Kj} and Min_Total_Cost(i, j) returns the total searching cost for the optimal BST for this set.
Let’s say we have created the optimal BST for this set of keys and ‘Kr’ is the root of this BST such that i <= r <= j, the tree would look like this:

Kr

/ \

Ki,…, Kr-1    Kr+1,…, Kj

The keys on the left of Kr in the given set will be part of left sub-tree and the keys on the right will be part of right sub-tree. If Total_Cost(i, j) gives the total searching cost for this BST, then it includes –

1. The searching cost of the root which is – level of root (1) * frequency of root key,
2. The total cost of the left sub-tree and the total cost of the right sub-tree (the sub-problems),
3. And as explained earlier that making the keys on the left and right of Kr in the given set the children of Kr will increase their path length by 1 and hence all these keys will incur that cost to the total cost, i.e. all keys which are yet to be included in the BST contribute a cost equal to their frequency to the total cost at every level, hence at each level we have sum of frequency of all such keys/nodes.
```Total_Cost(i, j) =  (Level of Kr * Freq of Kr)
+(Total searching cost of left sub-tree)
+(Total searching cost of right sub-tree)
+(Sum of frequency of all the keys in the
left sub-tree)
+(Sum of frequency of all the keys in the
right sub-tree)

= Total_Cost(i, r-1) +
Total_Cost(r+1, j) +
(Sum of frequency of all the keys {Ki,…,
Kj})```

Since we do not know the key Kr, we will have to try out each key in the set as root of the BST and we will keep track of the minimum of the total searching cost of the BSTs as we calculate them.
Using this formula above we can write for Min_Total_Cost(i, j) as –

```Min_Total_Cost(i, j) = min ( Min_Total_Cost(i, r-1)
+ Min_Total_Cost(r+1, j)
+ Sum of all Fx for x in
{i,..,j} )
for all r in {i,..,j}

If i > j which doesn’t make a valid set of keys, Min_Total_Cost(i, j) = 0.```

Also this shows this problem has optimal substructure (i.e. an optimal solution can be constructed from optimal solutions of subproblems).

### Recursive Approach:

Using this we can write a recursive implementation:

C++:

```#include <bits/stdc++.h>
using namespace std;

int Min_Total_Cost(int freq[], int i, int j)
{
if (i > j)
return 0;

int min_total_cost = INT_MAX;

for (int k = i; k <= j; ++k)
{
int total_cost = ( Min_Total_Cost(freq, i, k-1)
+ Min_Total_Cost(freq, k+1, j)
+ accumulate(freq+i, freq+j+1, 0));

if (total_cost < min_total_cost)
min_total_cost = total_cost;
}

return min_total_cost;
}

int getTotalCostOfOptimalBST(int keys[], int freq[], int num_keys)
{
return Min_Total_Cost(freq, 0, num_keys-1);
}

int main()
{
int keys[] = {0, 1, 2};
int freq[] = {34, 8, 50};
int n = sizeof(keys) / sizeof(keys);

cout<<"Total cost of Optimal BST:"<<getTotalCostOfOptimalBST(keys, freq, n)<<endl;

return 0;
}```

Java:

```import java.io.*;

class OptimalBST
{
static int sum(int freq[], int left_idx, int right_idx)
{
int sum = 0;
for (int i=left_idx; i <= right_idx; ++i)
{
sum += freq[i];
}
return sum;
}

static int Min_Total_Cost(int freq[], int i, int j)
{
if (i > j)
return 0;

int min_total_cost = Integer.MAX_VALUE;

for (int k = i; k <= j; ++k)
{
int total_cost = ( Min_Total_Cost(freq, i, k-1)
+ Min_Total_Cost(freq, k+1, j)
+ sum(freq, i, j));

if (total_cost < min_total_cost)
min_total_cost = total_cost;
}

return min_total_cost;
}

static int getTotalCostOfOptimalBST(int keys[], int freq[], int num_keys)
{
return Min_Total_Cost(freq, 0, num_keys-1);
}

public static void main (String[] args)
{
int keys[] = {0, 1, 2};
int freq[] = {34, 8, 50};
int n = keys.length;

System.out.println("Total cost of Optimal BST:" +
getTotalCostOfOptimalBST(keys, freq, n));
}
}```

But this implementation has exponential time complexity. To find the reason behind such high time complexity let’s have a look at the recursive function call tree:

In this example of a set consisting of 3 keys {0, 1, 2}, we can see that subproblems such as  Min_Total_Cost(freq, 2, 2) and Min_Total_Cost(freq, 1, 1) are calculated repeatedly.
Our recursive algorithm for this problem solves the same subproblem over and over rather than always generating new subproblems. These are called overlapping subproblems.

As the two properties required for using Dynamic Programming : ‘optimal substructure’ and ‘overlapping subproblems’ hold, we can use DP for this problem.

### Dynamic Programming Solution:

In DP we start calculating from the bottom and move up towards the final solution.
Hence we first solve the sub-problem {i=0, j=0}, then we skip all the sub-problems where (i > j), then next we solve {i=1, j=1}, and reuse solutions to these sub-problems to solve {i=0, j=1} and so on.
Finally we solve the sub-problem {i=0, j=(n-1)} and this gives us the final answer.

Solution of all subproblems are stored in a 2D array / DP table so that they can be reused when required.

C++:

```#include <bits/stdc++.h>
using namespace std;

long long int getTotalCostOfOptimalBST(int keys[], int freq[], int num_keys)
{
long long int DP_Table[num_keys][num_keys]{};

for (int j = 0; j < num_keys; ++j)
{
for (int i = j; i >= 0; --i)
{
long long int min_total_cost = INT_MAX,
sum_freq = accumulate(freq+i, freq+j+1, 0);

for (int k = i; k <= j; ++k)
{
long long int total_cost = 0,
total_cost_left_subtree = 0,
total_cost_right_subtree = 0;

if (k > i)
{
total_cost_left_subtree = DP_Table[i][k-1];
}

if (k < j)
{
total_cost_right_subtree = DP_Table[k+1][j];
}

total_cost = ( total_cost_left_subtree
+ total_cost_right_subtree
+ sum_freq );

if (total_cost < min_total_cost)
min_total_cost = total_cost;
}

DP_Table[i][j] = min_total_cost;
}
}

return DP_Table[num_keys-1];
}

int main()
{
int keys[] = {0, 1, 2, 3, 4, 5, 6};
int freq[] = {22, 18, 20, 5, 25, 2, 8};
int num_keys = (sizeof(keys) / sizeof(keys));

cout<<"Total cost of Optimal BST:"
<<getTotalCostOfOptimalBST(keys, freq, num_keys)<<endl;

return 0;
}```

Java:

```import java.io.*;

class OptimalBST
{
static int sum(int freq[], int left_idx, int right_idx)
{
int sum = 0;
for (int i=left_idx; i <= right_idx; ++i)
sum += freq[i];
return sum;
}

static int getTotalCostOfOptimalBST(int keys[], int freq[], int num_keys)
{
int DP_Table[][] = new int[num_keys][num_keys];

for (int j = 0; j < num_keys; ++j)
{
for (int i = j; i >= 0; --i)
{
int min_total_cost = Integer.MAX_VALUE,
sum_freq = sum(freq, i, j);

for (int k = i; k <= j; ++k)
{
int total_cost = 0,
total_cost_left_subtree = 0,
total_cost_right_subtree = 0;

if (k > i)
total_cost_left_subtree = DP_Table[i][k-1];

if (k < j)
total_cost_right_subtree = DP_Table[k+1][j];

total_cost = ( total_cost_left_subtree
+ total_cost_right_subtree
+ sum_freq );

if (total_cost < min_total_cost)
min_total_cost = total_cost;
}

DP_Table[i][j] = min_total_cost;
}
}
return DP_Table[num_keys-1];
}

public static void main (String[] args)
{
int keys[] = {0, 1, 2, 3, 4, 5, 6};
int freq[] = {22, 18, 20, 5, 25, 2, 8};
int num_keys = keys.length;

System.out.println("Total cost of Optimal BST is "
+ getTotalCostOfOptimalBST(keys, freq, num_keys));
}
}```

Time complexity: O(n^3)
Space complexity: O(n^2)

This article is contributed by Bhushan Agrawal.

Posted on Categories Algorithms, Binary Search Tree, Dynamic programmingLeave a comment on Optimal Binary Search Trees

## Maximal Rectangle

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area. For example:

```Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6```

Thoughts

The most basic solution involves calculating the area of the largest rectangle for each element in the matrix which is 1. We can implement this by iterating through the matrix in a top-down + left-right fashion, and checking for the largest rectangle that forms to its right and down sides.

To check for the largest rectangle, we can find the maximum length of each row of 1s to the right & below the current element. This might form either a rectangle, or an uneven surface. To calculate the area of the rectangle is easy, but to calculate the maximum area in an uneven surface is the problem of calculating the largest area in a histogram. This problem takes O(n) time, where n is the number of bars in the histogram. Counting the length of the bars is necessary too, which makes the total time to calculate an uneven surface’s area in our problem O(n * m).

This would make the brute force solution have a time complexity of O(n2 * m2) and a space complexity of O(min(n, m)) [because of largest area in a histogram].

Efficient solution

Once we figure out that we can effectively find the area of an uneven surface using the histogram algorithm, we realize that instead of iterating through the entire array, we can go row by row, calculating the current histogram at each level. This greatly optimizes the time needed to calculate the maximum area.

The way we implement it is to cumulatively add rows with consecutive ones as we go down the rows. The value is reset to 0 if a particular row value is 0. This gives us a histogram with the current row as the base and the lengths calculated so that we can find the current largest area. We keep track of the largest area found yet, and at the end of the iteration, we have the largest rectangle in the matrix.

### Show me the implementation

```class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if len(matrix) == 0 or len(matrix) == 0:
return 0
maxArea = 0
hist = [int(i) for i in matrix]

# Create a copy of the first row
# self.findLargestArea(histogram) is the helper
# function that calculates the area of the current histogram

maxArea = max(maxArea, self.findLargestArea(hist))

for i in range(1, len(matrix)):
# Add the previous row to the next row if it is one
hist = [hist[j] + int(matrix[i][j])
if int(matrix[i][j]) > 0 else 0 for j in range(len(matrix[i]))]

maxArea = max(maxArea, self.findLargestArea(hist))

return maxArea

def findLargestArea(self, inp: List[int]):
if len(inp) < 2:
return inp if len(inp) == 1 else 0
stack = []
maxArea = 0
for i in range(len(inp)):
if len(stack) == 0 or inp[stack[-1]] <= inp[i]:
stack.append(i)
else:
while len(stack) > 0 and inp[stack[-1]] > inp[i]:
current = stack.pop()
maxArea = max(maxArea,
(i - 1 - stack[-1] if len(stack) > 0 else i) * inp[current])
stack.append(i)

if len(stack) > 0:
i = len(inp)
while len(stack) > 0:
current = stack.pop()
maxArea = max(maxArea,
(i - 1 - stack[-1] if len(stack) > 0 else i) * inp[current])

return maxArea
```

The time complexity of this code is O(n * m) and the space complexity is O(n).

Questions: Can you do it in-place? Can you reduce the space usage in the code above?

Posted on Categories AlgorithmsLeave a comment on Maximal Rectangle

## Largest sum of non-adjacent numbers

Given an array of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.For example,

```Input:
[2, 4, 6, 2, 5]
Output:
13
Explanation:
Since we pick 2, 6, and 5.

Input:
[5, 1, 1, 5]
Output:
10
Explanation:
Since we pick 5 and 5.
```

## Thought process

This problem is very similar to the coin change problem, where for each coin we make a decision, whether to include or exclude a coin in the change or not.

In this problem as well, we make the choice for each number. What if we include a number at index i in the sum and what if we do not include it? If we include the number in the sum, which eventually may be the maximum sum, what can we do with the remaining numbers in the array? If we include a[i], then we definitely cannot include a[i+1], due to the constraint of non-adjacent numbers. After making the choice that we will include a[i] into the sum, our problem reduces to find the maximum sum of non-adjacent numbers from index i+2 to a.length-1.

What if I do not include this number a[i] in the sum? In that case, we can choose a[i+1] in the sum, so the problem reduces to find the largest sum of non-adjacent numbers in the array from index i+1 to a.length

We do not know which choice (to include or exclude a[i]) will give us the largest sum, so we try both and take the maximum of both.

Recursive implementation

```    public int sum(int[] a){
return sumUtil(a,0);
}

private int sumUtil(int[] a, int index){
if(index > a.length-1){
return 0;
}

return Math.max(a[index] + sumUtil(a, index+2),
sumUtil(a, index+1)
);
}
```

For each number we take two choices and follow them, overall complexity of above implementation is O(2n) where n is the length of the array.
Let’s see the execution tree of the recursive implementation with one of the examples, it looks like this: It is evident from the execution tree that there are many subproblems colored red, blue, and light blue as groups, which are solved again and again. This is called overlapping subproblems and is a necessary condition to think in dynamic programming terms. We already know that an optimal solution to subproblem leads to an optimal solution to the original problem, hence, we can apply the dynamic programming approach here.

The best way to avoid calculating subproblems, again and again, is to memorize what is already calculated, so let’s modify the code to use a cache, this approach is called a top-down approach.

Top down implementation

```    public int sum(int[] a){
int [] cache = new int[a.length];
return sumUtil(a,0, cache);
}

private int sumUtil(int[] a, int index){
if(index > a.length-1){
return 0;
}
if (cache[index] > 0){
return cache[index];
}

cache[index] = Math.max(a[index] + sumUtil(a, index+2),
sumUtil(a, index+1)
);
return cache[index];
}
```

There will be a maximum n calls to the `sumUtil()` function, so time complexity reduces to O(n) along space complexity of O(n).

How can we implement the bottom-up solution for this problem? If we defined a 1D array dp[] where dp[i] represents the maximum sum which can be achieved till index i of array. To include a[i] into that sum, we have to look for maximum sum that can be achieved till index i-2 i.e dp[i-2]. If we exclude the index, then we get the maximum sum till index i-1 i.e dp[i-1]. We take whatever is the maximum.
Recurrece relation is as follows.

```dp[i] = max(dp[i-2] + a[i], dp[i-1]);
```

Bottom up implementation

```   private int sumDP(int[] a){
if(a.length == 0) return 0;

if(a.length == 1) return a;
if(a.length == 2) return Math.max(a, a);

int [] dp = new int[a.length];

dp = a;
dp = Math.max(a, a);

int max = 0;
for(int i=2; i<a.length; i++){
dp[i] = Math.max(a[i] + dp[i-2], dp[i-1]);
max = Math.max(max, dp[i]);
}

return max;
}
```

The time complexity of bottom-up approach is also O(n) along space complexity of O(n).

Follow-up: Can you do this in constant space?

Posted on Leave a comment on Largest sum of non-adjacent numbers

## Is subsequence

Given a string s and a string t, check if s is subsequence of t. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not). For example:

```Input:
s="ace" ,t= "abcde"
Output:
True

Input:
s="aec" t="abcde"
Output:
False
```

## Approach

This problem looks similar to edit distance problem which can be solved using dynamic programming. The only difference is only deletions are allowed in this problem.

Recursive approach

What happens if we take a character at index i from string s and a character at index from string t? There are two possibilities: either these characters are equal or they are not equal. If the characters are equal, then we found the corresponding character in the target string, so we have to look for a remaining substring from index i+1 in s in substring in t from index j+1
What if the characters are not equal? In that case, we keep looking in substring of t from index j+1, but the index of s does not change, it remains at i, because we have not found the match for this character yet in the target string.

Implementation note: `s.substring(1)` actually get the substring of the string from the second character to the last character and achieves the increase in the indices as mentioned above.

``` private boolean isSubsequenceUtil(String s, String t){

if(s.length() == 0) return true;

if(t.length() == 0) return false;

return (s.charAt(0) == t.charAt(0)
&& isSubsequenceUtil(s.substring(1), t.substring(1)))
|| isSubsequenceUtil(s, t.substring(1));

}
```

If you run the above code in Leetcode, it will give you Time Limit Exceeded error, that becomes obvious when we draw the execution tree of the function, we will notice that we are solving the same problem multiple times.

Top down approach

The first thing we should do it to avoid solving the subproblem, again and again, that can be achieved using memorization. We introduce a caching place to store if we have solved the problem already and if yes, what was the result. If we already have solved the problem, we will just use the result and not solve the problem again. Below is the memorization code.

``` private boolean isSubsequenceUtil(String s, String t, boolean[][] isKnown,
boolean[][] value,
int sIndex, int tIndex){

if(s.length() == sIndex) return true;

if(t.length() == tIndex) return false;

if(isKnown[sIndex][tIndex]){
return value[sIndex][tIndex];
}

value[sIndex][tIndex] = (s.charAt(sIndex) == t.charAt(tIndex)
&& isSubsequenceUtil(s, t, isKnown, value,
sIndex+1, tIndex+1))
|| isSubsequenceUtil(s, t, isKnown, value, sIndex, tIndex+1);

isKnown[sIndex][tIndex] = true;

return value[sIndex][tIndex];
}
```

This code passes all the test cases at Leetcode. This approach is called a top-down approach in dynamic programming, where we start with the top, keep solving smaller problems until we find a solution for the original problem.

Bottom up approach

Since the optimal solution to the subproblems leads to optimal solution to the original problem, we can apply another approach called the bottom-up approach. In this approach, we start from the smallest possible problem and build our solution upwards.

What is the smallest problem possible in this case? If string s is empty and target string t is not empty, s is definitely a subsequence although an empty one.
So, if I create a two dimensional array where rows represent the number of characters in t and column represent number of characters in s, then I can initialize the first column (which represents zero length of the source string) as

```for(int i=0; i<=t.length(); i++){
dp[i] = true;
}
```

Other way around, what if string t is empty and string s is not empty, then there is no way possible string s can be subsequence of string t, this can be filled in the table as follows:

```for(int i=0; i<=t.length(); i++){
dp[i] = false;
}
```

What if we move up a bit, let’s say we have i characters in string t and j characters in string s. We compare the i-th character with j-th character and see if there are equal?
If they are equal and if string t with i-1 characters already has string s with j-1 characters as subsequence, then we can mark that string t with i characters has string s with j characters as subsequence too.

If the characters are not equal, then either string s with j characters should already be subsequence in i-1 characters of string t, or it cannot be a subsequence in i characters either.

```dp[i][j]= t[i] == s[j] && dp[i-1][j-1]
dp[i][j]= dp[i-1][j]
```

If we go through each character in both string. One implementation note, i and j represent the length of strings and not the index, that is why we compare characters at index i-1 and j-1 when solving for dp[i][j]. Also if length of t is less than length of s there is no way s can be subsequence of t.

```     private boolean isSubsequenceUtilDP(String s, String t){

boolean [][] dp = new boolean[t.length()+1][s.length()+1];

for(int i=0; i<=t.length(); i++){
dp[i] = true;
}
for(int j=1;j<=s.length(); j++){
dp[j] = false;
}

for(int i=1; i<=t.length(); i++){
for(int j=1; j<=s.length(); j++){
if(i < j) dp[i][j] = false;

else {
dp[i][j] = t.charAt(i-1) == s.charAt(j-1) ?
dp[i-1][j-1]
: dp[i-1][j];
}
}
}

return dp[t.length()][s.length()];
}
```

The time complexity of dynamic programming solution is O(n * m) where n and m are length of string t and s respectively. Also, there is additional space complexity of O(n * m).

We can reduce this complexity by using stack data structure as the relative position of characters in source and target string should remain same and matched characters can be deleted.

Using Stack

1. Push the characters of source string in reverse order onto the stack.
2. Iterate through the characters of the target string, and check if the character matches with the top element of the stack. If it matches, pop the element from the stack.
3. Obtain the end result – If size of stack is zero, then it returns true, else false.
```public boolean isSubsequence(String s, String t) {
if(s.length()==0 && t.length() > 0)
return true;

if(s.length() > t.length())
return false;

Stack<Character> stack=new Stack<>();
for(int i=s.length()-1;i >=0;i--)
stack.push(s.charAt(i));

for(int i=0; i < t.length();i++){
if(!stack.isEmpty() && t.charAt(i)==stack.peek())
stack.pop();
}
return stack.isEmpty();
}
```

Time Complexity of the stack based solution is O(n + m) and the space Complexity isO(m), where n and m are length of string t and s respectively

The space complexity can be further reduced to O(1) by using two pointers approach.

Two Pointers

Take two pointers i which is used to traverse string t and j, which is used to traverse strings. Increment j whenever there is a match and compare the value of j with the length of source string at the end.

```public boolean isSubsequence(String s, String t)
{
if(s.length() > t.length())
return false;
int i = 0, j = 0;
while(i < t.length() && j < s.length()){
if(t.charAt(i) == s.charAt(j))
j++;
i++;
}
if(j == s.length())
return true;
return false;
}
```

The time Complexity is O(n + m) and the space Complexity is O(1)

Please write to us if something is missing or wrong, we will be happy to fix it.

Posted on Leave a comment on Is subsequence

## Cutting rods problem

Given a rod of length ‘n’ units and list of prices of pieces of lengths ‘1’ to ‘n’, the problem is to determine the maximum value that can be obtained by cutting the rod and selling the pieces.
For eg.

```Input:
Rod is of length 4 and list of prices is:
Piece length 1 2 3 4
Price 2 5 7 8
Output:
10
Explanation:
The maximum value that can be obtained in this case is ‘10’ by cutting the rod in pieces of length {2, 2}.
```

## Thought process

One might get tempted to use a Greedy approach for solving problems where we need to find either minimum or maximum values, but remember that for the Greedy approach one has to give proof of its correctness as it takes just a single example/test case to prove that Greedy approach fails. Hence in general such problems are solved using DP.
Solution Approach:
To find the maximum value using the price list and length of the rod, instead of considering the extremes (like we do in Greedy) from the given input, we consider all the input values. Meaning, in a Greedy approach one might consider cutting the rod in pieces with the highest available price only so that he can obtain the maximum value, but this approach fails in case of the example above.

Hence to find the maximum value we will consider cutting the rod in pieces of all possible lengths, i.e. for a rod of length ‘4’, if get_max_val(price_list, rod_length = 4) gives the maximum value, then:
We’ll first consider making a cut at length 1: This gives us a piece of length 1 and we can sell this piece to get value 2.
Now we are left with the remaining rod of length 4 – 1 = 3. The problem now reduces to finding the maximum value that can be obtained from a rod of length 3 with the same input price list. The total value that can be obtained in this configuration will be:

2 + get_max_val(price_list, rod_length = 3).

Similarly, we can make a cut at length 2: this gives us a piece of length 2 and we can sell this piece to get value 5.

Now we are left with the remaining rod of length 4 – 2 = 2. The problem now reduces to finding the maximum value that can be obtained from a rod of length 2 with the same input price list. The total value that can be obtained in this configuration will be:

5 + get_max_val(price_list, rod_length = 2).

Also, we can make a cut at length 3: This gives us a piece of length 3 and we can sell this piece to get value 7.

Now we are left with the remaining rod of length 4 – 3 = 1. The problem now reduces to finding the maximum value that can be obtained from the rod of length 1 with the same input price list. The total value that can be obtained in this configuration will be:

7 + get_max_val(price_list, rod_length = 1).

We can also sell the complete rod of length ‘4’ as it is, which will fetch us the total value => 8

For each sub-problem, we’ll take a similar approach of cutting the current piece of a rod into pieces of length ranging from ‘1’ to ‘current rod length’. We keep cutting the rod and solving the resulting sub-problems till the length of the rod reaches zero. While trying out these different configurations we will keep a track of the maximum of the total value of each configuration.

The approach discussed above shows that this problem has optimal substructure (i.e. an optimal solution can be constructed from optimal solutions of subproblems).

Let’s try to implement this using recursion:
C++:

```#include <iostream>
#include <vector>
using namespace std;

int get_max_value(vector<int>& price_list, int  rod_length)
{
if(rod_length <= 0)
return 0;
int max_value = 0;
for(int i=0; i<rod_length; i++)
{
max_value = max(max_value,
price_list[i]
+ get_max_value(price_list, rod_length - i - 1)
);
}
return max_value;
}

int main(void)
{
vector<int> price_list{2, 5, 7, 8};
int rod_length = 4;
cout<<get_max_value(price_list, rod_length)<<endl;
return 0;
}
```

Java:

```import java.io.*;

class rod_cutting
{
static int max(int a, int b)
{
return (a < b) ? b : a;
}

static int get_max_value(int price_list[], int rod_length)
{
if (rod_length <= 0)
return 0;

int max_value = 0;

for(int i=0; i<rod_length; ++i)
{
max_value = max(max_value,
price_list[i]
+ get_max_value(price_list, rod_length - i - 1)
);
}

return max_value;
}

public static void main(String args[])
{
int price_list[] = new int[] {2, 5, 7, 8};
int rod_length = price_list.length;
System.out.println(get_max_value(price_list, rod_length));
}
};
```

But this recursive implementation has exponential time complexity. Let’s have a look at the function call tree to understand the reason behind this: In this example of finding max value for a rod of length = 4 and a list of prices for its pieces, subproblems such as get_max_value(price_list, 2) and get_max_value(price_list, 1) are calculated repeatedly. Our recursive algorithm for this problem solves the same subproblem over and over rather than always generating new subproblems. These are called overlapping subproblems.
As the two properties required for using Dynamic Programming: optimal substructure and overlapping subproblems hold, we can use DP for this problem. Unlike recursion, Dynamic Programming uses a bottom-up approach.

## Dynamic Programming Approach

In DP we start calculating from the bottom and move up towards the final solution. The solutions of all subproblems are stored in a 2D array / DP table so that they can be reused when required.

```#include <iostream>
#include <vector>
using namespace std;

int get_max_value(vector<int>& price_list, int  rod_length)
{
int dp_table[rod_length+1][rod_length+1] = {};

for (int i = 1; i <= rod_length; i++)
{
for (int j = 1; j <= rod_length; j++)
{
if(j >= i)
{
dp_table[i][j] = max(dp_table[i-1][j],
price_list[i-1] + dp_table[i][j-i]);
}
else
{
dp_table[i][j] = dp_table[i-1][j];
}
}
}

return dp_table[rod_length][rod_length];
}

int main(void)
{
vector<int> price_list{2, 5, 7, 8};
int rod_length = 8;
court<< get_max_value(price_list, rod_length)<<endl;
return 0;
}
```

The time complexity of the solution is O(n2) along with space complexity of O(n2) Where n is rod length.

The space complexity of the DP code can be reduced by skipping storing solutions of each subproblem so that instead of a 2D array we can work with a 1D array.

With a 2D array, we were storing solutions for subproblems that have a particular rod length with a subset of given price_list, but instead of this for a particular rod length we can compare total values obtained from all subproblems and storing only the maximum value, this way using a 1D array suffices.
But also note that a question, if asked, that what cuts were actually made to get the maximum value, cannot be answered with a 1D array solution. In 2D array, we can traverse back starting from dp_table[rod_length][rod_length] and check if the value at the current cell is calculated from the same row and if that’s the case then the current row number is considered as one of the piece lengths that were cut to get the maximum value.

```import java.io.*;

class rod_cutting
{
static int max(int a, int b)
{
return (a < b) ? b : a;
}

static int get_max_value(int price_list[], int rod_length)
{
int dp_table[] = new int[rod_length+1];
dp_table = 0;

for (int i=1; i <= rod_length; ++i)
{
int max_value = 0;

for (int j=0; j < i; ++j)
{
max_value = max(max_value,
price_list[j] + dp_table[i - j - 1]);
}
dp_table[i] = max_value;
}

return dp_table[rod_length];
}

public static void main(String args[])
{
int price_list[] = new int[] {2, 5, 7, 8};
int rod_length = price_list.length;
System.out.println(get_max_value(price_list, rod_length));
}
};
```

The time complexity remains same O(n2) but the space complexity reduces to O(n) where n is rod length.

This article is contributed by Bhushan Aggrawal.

Posted on Categories Dynamic programmingLeave a comment on Cutting rods problem