## Single number in an array

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

```Example 1:
Input: [2,2,1,3,4,3,5,4,5,]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4```

Approach 1

You will be thinking it’s a very simple problem. What we all need to do is to take count of each distinct number and that number having count 1 will be our answer. We can achieve it by using a dictionary.

Time Complexity – 0(N)
Space Complexity – 0(N)

What if your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? It means you have to solve the problem in O(N) time complexity and constant space that means space complexity must be O(1).

Think of an approach before going into the post.

Let me tell you, have you ever heard of Bit Manipulation?

‘’ As the name suggests, it is a process of performing logical operations on bits to achieve the desired result.’’

To understand the bit manipulation let’s first have a look at Logical Bitwise Operators.

1. AND (&)
2. OR ( | )
3. XOR (^)
4. Left Shift (<<)
5. Right Shift (>>)

In our particular problem, we will implement Bitwise XOR to get the desired result.

Properties of Bitwise XOR (^)–

1. 0 ^ 0 = 0
2. 0 ^ 1 = 1
3. 1 ^ 0 = 1
4. 1 ^ 1 = 0

If we observe the above operations we find that XOR of the same bits results in 0 and XOR of two different bit results into 1.

Now, Let’s have a look on some other examples –

• 1 ^ 1 ^ 1 ^ 1 = 0
• 2 ^ 2 = 0
• 1 ^ 1 ^ 2 = 2
• 2 ^ 3 ^ 4 ^ 3 ^ 2 = 4 (XOR operation is commutative and associative)

Now pause and observe the above examples very carefully.

Approach 2

So, If you observe carefully you will find that XOR of all those numbers appearing twice are being cancelled out and we are left with the number that appears only once. It clearly means if there are N numbers out of which N-1 numbers appears twice (or even number of times) and one number appear only once, then XOR of all numbers collectively results into that number which appears only once (See Examples 6, 7, 8) and as a result we will get our desired number.

As in example 8, 2 appears twice (so 2 ^ 2 = 0) and 3 appears twice (3 ^ 3 = 0) and 4 appears only once so as a consequence we will get 4 (0 ^ 0 ^ 4 = 4)

So in order to solve our particular problem we need to find XOR of all the numbers of array and and resultant XOR will be our answer.

Python Solution –

```def singleNumber(Arr, n):
ans=0
for i in range(N):
ans^=Arr[i]
return ans

```

Steps-

1. Iterate over all elements of array
2. Find the XOR of all elements of array and store it into a variable ans.
3. Return ans.

Complexities –

1. Time Complexity – O(n)
2. Space Complexity- O(1)

This article is contributed by Md Taslim Ansari

Posted on Categories Amazon Interview questions, Leetcode problemsLeave a comment on Single number in an array

## Arrays With Elements In The Range 1 to N

When an array has all its elements in the range of 1 to N ( where N is the length of the array ) we can use the indices to store the ordered state of the elements in the array. This ordered-state can in-turn be used to solve a variety of problems which we’ll explore soon. First, a very simple demonstration of this property.

Here is an array which has unique elements in the range of 1 to N.
Given array (A) : 5,3,1,4,2
Indices:                0,1,2,3,4

Sort in Linear Time

The first use-case of this unique property is being able to sort in O(N) time i.e. a special-case(all unique elements) of the Counting Sort. The crux of this sort is to check whether an element is at its corresponding index and swap it to its correct index if it’s not. Following is a demonstration of this logic:

Given array (A) : 5,3,1,4,2
Indices:                0,1,2,3,4

For each A[i] check if A[A[i] – 1] equals A[i] or not. If they are not equal then swap element at A[A[i] – 1] with A[i]. Basically the correct value for any index i is when A[i] contains i+1.

In the above case, let’s start with i = 0.

A[A – 1] or A[5-1] orA which is 2 and A = 5. This means that A[A[i] – 1] is not equal to A[i] and hence not in its correct position. So we need to swap in order to put A -> 5 to its correct position which is index 4 and A will hold 4 after the swap. Similarly, we need to repeat this check & swap for all the elements.

What if we cancel-out the common terms and modify the check from  `A[i] != A[A[i] - 1]` to `i != A[i]-1` ?

Find The Missing Integer

A similar approach can help us find the smallest missing positive-integer in a given array. By smallest missing positive-integer, we just mean the smallest positive integer that does not exist in the given list of numbers. For example:

Given Array: `-2, 3, 0, 1, 3`
In the above case, the smallest missing positive integer is 2.

If we were to apply the usual sorting techniques and then scan the array for the smallest positive integer absent it would imply a time-complexity of O(NLog(N)) + O(N). We can definitely do better than this! At first glance, it seems that this problem does not lie within the unique property of elements being in the range of 1 to N since the numbers in the given array are well outside the range, but to solve this problem we still only need to figure out whether we have elements from 1 to N present in the given array or not.

How do we know whether the given array has elements from 1 to N? We can use the counting-sort discussed earlier to put each element in its “correct position”, i.e index 0 should hold 1, index 1 should hold 2 and so on. The smallest index that does not hold its correct element is the missing integer.

If we sort the given array using counting sort described above, we will get: `1, 0, 3, -2, 3`. And the smallest index `i` to not hold its correct value i.e. `i+1` will give us the answer to the smallest missing positive integer. In this case, that index is 1 since it does not hold 2, thus the smallest positive missing integer is 2.

Find The Duplicate Element

The third use-case of this property is to figure out the duplicate elements without using any extra space. We can iterate over the array A and mark the corresponding index of the encountered element as negative – unless it has already been marked negative! For example: if A = 3 (or -3 ) then mark `A[ Abs - 1]` as negative, this way whenever we encounter 3 (or -3) again in any of the A[i] we will know that the value 3 has been visited before since A[3-1] will be negative.

Given array (A) : 5,3,1,4,3
Indices:                0,1,2,3,4

When we encounter A i.e. 5, we make A[5-1] i.e. A negative, so the array becomes:
`5,3,1,4,-3`
Next, we encounter A i.e. 3, we make A[3-1] i.e. A negative, so the array becomes:
`5,3,-1,4,-3`
Next, we encounter A i.e. -1, we make A[1-1] i.e. A negative, so the array becomes:
`-5,3,-1,4,-3`
Next, we encounter A i.e. 4, we make A[4-1] i.e. A negative, so the array becomes:
`-5,3,-1,-4,-3`
Next, we encounter A i.e. -3, we want to make A[3-1] i.e. A negative, but in this case, A is already negative thus we know that A has been visited before! Which means `Abs(A)` i.e 3 is the duplicate element.

Here is a snippet to demonstrate the code for sorting an array in linear time as per the above approach. The exact same approach can be used to solve the other two applications i.e. Finding the Duplicate and Finding The Missing Integer.

```        int swap=0;

for(int i = 0; i < nums.length;){

if(nums[i] > 0 && nums[i] < nums.length) {

if(nums[nums[i]-1] != nums[i]){
swap = nums[i];
nums[i] = nums[nums[i] - 1];
nums[swap - 1] = swap;
}else{
i++;
}

}else{
i++;
}
}
```

If you are preparing for a technical interview in companies like Amazon, Facebook, etc and want help with preparation, please register for a coaching session with us.

Posted on Leave a comment on Arrays With Elements In The Range 1 to N

# Combination sum problem

Given an array of integers (`candidates`) (without duplicates) and a target number (`target`), find all unique combinations in `candidates` where the candidate numbers sums to `target`.

Also, the same candidate can occur in the combination multiple times.

For example, Input: candidates = [4,3,5,9], target = 9, a solution set is:[ , [3,3,3], [4,5]]

How can do we go about it? What happens if I take the coin 4 in the current example? Then all need to find in the `candidates` array if there is a combination adds up to 9-4 = 5. It seems like a recursion. For recursion, we need a termination condition. In this case, if I have on candidates to add and `target` is greater than zero, then whatever combination I have till now has no value, so I terminate the recursion in this case.

Second what if I have already found a combination that adds up to `target`? Then I will put that combination in the list of combinations and return.

What happens in recursive implementation? Well, we go through each coin, add that to the current combination and see if leads to the target? If it does, it will be added to the result list along with the list of other candidates. If not, we just remove the current coin (backtrack) from the current combination and try the next coin.

This approach is called the exhaustive search and backtracking paradigm of problem-solving where you search the entire input set to see to find the answer. However, in this case, we can prune the search path as soon as we know that the current set of candidates add up more than the target.

## Combination sum : implementation

```class Solution {
public List<List<Integer>> combinationSum(int[] candidates,
int target) {
/* The result list contains all the combination
which add up to target.
*/
List<List<Integer>> result = new ArrayList<List<Integer>> ();

//We start with the first coin and search exhaustively.
combinationSumUtil(candidates,
target,
result,
new ArrayList<Integer>(),
0
);

return result;

}

public void combinationSumUtil(int[] candidates,
int target,
List<List<Integer>> result,
List<Integer> current,
int index){

/*
First termination condition: if there are no coins left
and required target is more than zero.
*/
if(target > 0 && index == candidates.length){
return;
}

/*
Second termination condition: if target is zero,
we can add the current combination to the result
*/
if(target == 0 && index < candidates.length){
result.add(new ArrayList<>(current));
return;
}

/*
Start from the current index, and go through
all the coins.
*/
for(int i=index; i<candidates.length; i++){
/*
This is where we prune the branches
of our exhaustive search
*/
if(target - candidates[i] >=0){
current.add(candidates[i]); // add to the list
combinationSumUtil(candidates,
target-candidates[i],
result, current, i);

/* Remove the candidate from the list and
check other combinations.
*/
if(current.size() > 0)
current.remove(current.size()-1);
}
}

}
}
```

The time complexity is C(n,1) + C(n,2) + … + C(n,n) = 2^n – C(n,0) = `O(2n)`.

The beauty of this solution is that it works with negative candidates as well, where the Dynamic programming solution for it may not work.

Posted on Leave a comment on Combination sum problem

# Design a data structure with insert delete and getRandom in O(1)

The problem statement is to design a data structure which performs the following operations in O(1) time complexity:
1. Insert an element, `insert(int value)`
2. Remove an element, `remove(int value)`
3. Get random element, `getRandom()`

For example, insert 1 into the data structure insert(1): 
insert 2 into the data structure insert(2): [1,2]
insert 3 into the data structure insert(3): [1,2,3]

Remove 2 from it, remove(2). [1,3]
getRandom() should return 1 and 3 with equal probabilities.

These kind of problems are easy and hard at the same time. Idea is to go step by step and solve each part. The first step is to define an interface for this data structure, which is easy given the definition of the problem.

```public interface IRandomNumberGenerator {
public boolean insert(int value);
public boolean remove (int value);
public int getRandom();
}
```

Now that interface is ready, time to start implementing the class which implements this interface. First of all, we have to find a container to store all the elements. If we take an ArrayList, `insert()` is O(1) as we will always add new element at the end of the ArrayList. `getRandom` is also O(1). However, there is problem with `remove()`. To remove an element from ArrayList, we have to scan the whole ArrayList and remove the element, the move all the elements on the right of the deleted element to one index left. This is O(n) operation.

## Insert delete and getRandom in O(1): selection of data structures

A problem with storing elements in an ArrayList is that while removal, we have to scan the list and find the location of the element to be removed. What if we already knew the location of the element? If we store the position of each element in ArrayList in a HashMap which maps the value to its index on ArrayList

Now, `insert()` has to insert a value to two data structures, first into the ArrayList and then the location of the value in ArrayList to the HashMap. Remove operation can simply go to the location in the ArrayList and delete the element. Wait, still, we have to move all the elements on the right one position left. It means the worst case complexity of `remove()` still O(n).

We know one thing: if I remove the last element from the ArrayList then there is no shifting required. What if we copy the last value at the index of the element to be removed and then just remove the last element. Be careful, we have to update the HashMap with the new value for the element at the last index of ArrayList. In this way, `remove()` is also O(1).

### Insert, delete and getRandom in O(1): implementation

```package AlgorithmsAndMe;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class RandomNumberGenerator implements IRandomNumberGenerator {

private ArrayList<Integer> list;
private Map<Integer, Integer> loc;
private Random random;

//Initializing the class
public RandomNumberGenerator(){
list = new ArrayList<>();
loc = new HashMap<>();
random = new Random();
}

@Override
public boolean insert(int value) {
/*If hash already contains key then it is a duplicate key.
So, we just return false.
*/
if(loc.containsKey(value)) return false;

//Insert into list
list.add(value);

//Save the location on hash map
loc.put(value, list.size()-1);
return true;
}

@Override
public boolean remove(int value) {
/* If there is no entry in hash, that means
there is no element in ArrayList */
if(!loc.containsKey(val)) return false;

int location = loc.get(val);
//Remove from hash
loc.remove(val);

if(location != list.size()-1){
/*Copy the last value in the array
list to the current location*/
list.set(location, list.get(list.size()-1));

//Update the location of last element in hash
loc.put(list.get(location), location);
}

//remove the last location from ArrayList
list.remove(list.size()-1);

return true;
}

@Override
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
}

```
```package AlgorithmsAndMe;

import static org.junit.Assert.*;

public class RandomNumberGeneratorTest {

RandomNumberGenerator randomNumberGenerator =
new RandomNumberGenerator();

@org.junit.Test
public void testInterface() {
assertEquals(true, randomNumberGenerator.insert(4));
assertEquals(true, randomNumberGenerator.insert(5));
assertEquals(true, randomNumberGenerator.insert(3));
assertEquals(true, randomNumberGenerator.insert(2));

assertEquals(true, randomNumberGenerator.remove(4));

int random = randomNumberGenerator.getRandom();
System.out.println(random);
}
}
```

The complexity of the whole data structure for insert, delete and getRandom is O(1).

#### Insert, delete and get random when duplicates are allowed

Let’s make this problem a bit more complex by making duplicate elements possible in the list. The first problem with the existing implementation is that it stores the location of an element in ArrayList in a HashMap. If the same element can appear multiple times in the list, then which location should we store? We should store all the locations. It will change the definition of our HashMap as

```Map<Integer, HashSet<Integer>>
```

Hashset implements the Set interface, backed by a hash table which is actually a HashMap instance. No guarantee is made as to the iteration order of the set which means that the class does not guarantee the constant order of elements over time, that is what we require. We require that insert and remove operation on this data structure should be O(1) or constant time complexity.
To know more about the complexity of various data structures in Java, follow Runtime Complexity of Java Collections and read reason why HashSet provides constant time insert and remove operations.
Everything else follows the same process. To `insert()`, we should insert the location of the element at the HashSet in the hash table. While removing we find the last location of the element, put the last element of ArrayList in that location and update the HashSet of the location corresponding to the value at the last index of the ArrayList. Remove the last element from ArrayList.
We also have to move the last element in ArrayList of location in Hash, which is O(1) operation.

`getRandom()` implementation remains same.

```package AlgorithmsAndMe;

import java.util.*;

public class RandomNumberGenerator implements IRandomNumberGenerator {

private ArrayList<Integer> list;
private Map<Integer, HashSet<Integer>> loc;
private Random random;

//Initializing the class
public RandomNumberGenerator(){
list = new ArrayList<>();
loc = new HashMap<>();
random = new Random();
}

@Override
public boolean insert(int value) {

if(!loc.containsKey(value)){
loc.put(value, new HashSet<>());
};

//Insert into list
list.add(value);

//Save the location on hash map
loc.get(value).add(list.size()-1);
return true;
}

@Override
public boolean remove(int value) {
/* If there is no entry in hash, that means
there is no element in ArrayList */
if(!loc.containsKey(value)) return false;

//Get the last location of the element in ArrayList
HashSet<Integer> listLocations = loc.get(value);
int location = listLocations.iterator().next();
loc.get(value).remove(location);

int lastElement = list.get(list.size()-1);
if( lastElement != value) {
/*Copy the last value in the array
list to the current location*/
list.set(location, lastElement);
//Update the location of last element in hash
loc.get(lastElement).remove(list.size()-1);
loc.get(lastElement).add(location);
}
//remove the last location from ArrayList
list.remove(list.size()-1);

if(listLocations.isEmpty()) loc.remove(value);
return true;
}

@Override
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
}

```

Other problems which are very similar to this concept are: design an LRU cache, first non-repeated character in stream etc.

Please share if there is anything wrong or missing. If you are preparing for an interview and need one to one personalized coaching, please reach out to us on [email protected]

Posted on Leave a comment on Data structure with insert delete and getRandom in O(1)

## Merge overlapping intervals

Given N intervals S = {E1,E2,…..En} with each Ei has start time si and end time ei. Some of these intervals are overlapping. The problem statement is to merge these overlapping intervals.

Ei and Ej overlap when start time of Ej i.e sj is less than end time of Ei i.e ei.

For example:

```Input:
[(1,3),(2,4),(5,8), (6,9)]
Output:
[(1, 4),(5,9)]
Explantion:
Interval (1,3) and (2,4) and interval (5,8) and (6,9) overlap.
``` ## Merge overlapping intervals solution

As we always do, first try to come up with brute force solution, given enough time and space and money, how would you solve this?
The natural course is to take ith interval and compare start time of all jth intervals with end time of ith, if the start time of jth interval is less than the end time of ith event, then you can merge intervals. What should be end time for merged interval then?  It should be a maximum of end times of two merged intervals.

What will be the time complexity of this approach? We are not using any additional space, however, the worst-case time complexity is O(n2). Can we do better?

What are two times we are comparing in brute force solution? It’s the start time of one interval with the end time of another. If we arrange input in a specific order, can we reduce processing some entries?

If we sort all intervals based on their start time, si < si+1< si+2. Also, interval is always forward looking, ei > si, ei+1 > si+1 and so on.

If si is greater ei-1, then si+1 will be greater than ei-1, so no need to compare si+1 with ei-1, that is no need to go beyond immediate previous interval for any interval Ei.

If si is less than ei-1, update ei-1 with maximum of ei-1 and ei and move to Ei+1.

Notice that we need last interval Ei-1 to decide if to merge new interval into previous one or keep it as standalone. A stack is the best data structure to use. The algorithm will look like:

1. Consider interval Ei.
2. If stack is empty, push Ei to stack.
3. If stack is not empty, then pop interval at top of stack call it Ei-1.
4. Compare si, start time of Ei with ei-1, end time of Ei-1.
5. If si less than ei-1, update ei-1 as max(ei-1, ei), as in maximum of end times of two intervals and push back Ei-1on to stack.
6. Else push Ei on to stack.
7. Continue till all events are considered.
8. At the end of processing, stack will contain all merged interval.

Let’s take an example and see how this algorithm works. We have following intervals and we have to merge overlapping intervals.  Find the maximum of end times of two intervals and update the previous interval with that end time and push it back on to stack.

At this point, when there is no more interval remaining, the stack contains all merged overlapping intervals.

### Merge intervals Java implementation

```package com.company;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;

/**
* Created by sangar on 8.4.18.
*/
public class OverlappingIntervals {
public  static ArrayList<Interval>
mergeOverlappingIntervals(ArrayList<Interval> intervals){

ArrayList<Interval> mergedIntervals = new ArrayList<>();
Stack<Interval> s = new Stack();

//Sort the ArrayList of interval based on start time.
Collections.sort(intervals, Comparator.comparing(p -> p.getStartTime()));
for(Interval currentInterval : intervals){
if(s.empty())s.push(currentInterval);
else {
Interval previousInterval = s.pop();
if(previousInterval.getEndTime() >
currentInterval.getStartTime()){
/*
If current interval's start time is less than end time of
previous interval, find max of end times of two intervals
and push new interval on to stack.
*/
int endTime = Integer.max(previousInterval.getEndTime(),
currentInterval.getEndTime());
/* Notice that we have created new interval and
did not update the old one
This concept is called as immutability of class
*/
s.push(new Interval(previousInterval.getStartTime(),
endTime));
}
else{
s.push(previousInterval);
s.push(currentInterval);
}
}
}
while(!s.empty()){
mergedIntervals.add(s.pop());
}

return mergedIntervals;
}

public static void main(String[] args) {
ArrayList<Interval> intervals = new ArrayList<>();

intervals.add(new Interval(1,3));
intervals.add(new Interval(2,4));
intervals.add(new Interval(5,8));
intervals.add(new Interval(6,9));
ArrayList<Interval> mergedIntervals
= mergeOverlappingIntervals(intervals);
for (Interval interval : mergedIntervals){
System.out.print("(" + interval.getStartTime() +","
+ interval.getEndTime() + ")");
}
}
}
```

Complexity of algorithm to merge overlapping intervals will be O(nlogn) due to sorting with O(n) extra space for stack and then copying into the list to return also takes O(n) space.

There is another way to implement the same function without using the stack, here we use the fact that ArrayList in Java is implemented using the array as the base and getting an element at a particular index should be O(1) operation. The code looks more or less the same, however, there is no traversal of the stack at the end to create the list to return.

find overlapping intervals

```public List<Interval> mergeOptimized(List<Interval> intervals) {

if(intervals.size() == 0) return intervals;

Collections.sort(intervals,
(Interval a, Interval b) -> a.getStartTime() - b.getStartTime());

List<Interval> mergedIntervals = new ArrayList<Interval>();
for(Interval interval : intervals){

/*If the merged list is empty add the interval to
it or check if the last interval in merged list overlaps

/*Remember the get function on ArrayList is O(1) operation
because Arraylists in Java are backed by arrays */
if(mergedIntervals.isEmpty()
|| mergedIntervals.get(
mergedIntervals.size()-1).getEndTime() <
interval.getStartTime() ){
mergedIntervals.add(interval);
}
else {
int lastEndTime = Math.max(
mergedIntervals.get(mergedIntervals.size()-1)
.getEndTime(),
interval.getEndTime()
);
mergedIntervals.get(mergedIntervals.size()-1)
.setEndTime(lastEndTime);
}
}

return mergedIntervals;
}
```

You can use the above snippet of code to submit for this leetcode problem and it should be accepted.

Please share if there is something missing or wrong. Also, please reach out to us at [email protected] if you want to contribute to the website and help others to learn by sharing your knowledge. If you are preparing for an interview and need some coaching to prepare for it, please sign up for the free session with us.

Posted on 1 Comment on Merge overlapping intervals

# Word break problem

This problem is commonly asked in the Google and Amazon interview. We all know that if you typed string in Google search box does not make sense, Google breaks that into meaningful words and asks us back if we meant those words instead of a single word. This post discusses how can we find if the given string can be broken into meaningful dictionary words. For example, if I typed algorithmsandme and given dictionary is [“algorithms”, “and”, “me”], this string is breakable in meaningful words. but if the string is algorithmsorme this is not breakable into meaningful words. You can find this problem for practice at leetcode.

## Word break problem : thoughts

We start with the first character of the string, check if the character itself is a word in the dictionary? If yes, then our problem reduces to the smaller problem, that is to check if substring from index 1 to s.length is breakable or not.
If not, then we check two characters and then three characters and so on till we can check the whole string. As with every character inclusion, the problem reduces in size but remains the same, so ideal case for recursive implementation.

```package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

public boolean wordBreak(String s, List<String> wordDict) {
return wordBreakUtil(s, wordDict, 0, table);
}

private boolean wordBreakUtil(String s,
List<String> wordDict,
int index) {

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

boolean isBreakable = false;
for(int i=index; i<s.length(); i++) {
isBreakable = isBreakable
|| wordDict.contains(s.substring(index, i+1))
&& wordBreakUtil(s, wordDict, i + 1);
}

return isBreakable;
}
}

```

If you notice we are solving the same problems again and again in recursive function `wordBreakUtil`, how can we save that repeated calculations? Best way to save the already solve problems in a cache, that way we can refer to the cache if the problem is already solved or not. If yes, do not solve it again and use the cached value. This approach is called a Top Down approach and uses memoization to avoid repeated subproblems.

```package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

public boolean wordBreak(String s, List<String> wordDict) {
int [] table =  new int[s.length()];
for(int i=0; i<s.length(); i++){
table[i] = -1;
}
return wordBreakUtilTopDown(s, wordDict, 0, table);
}

private boolean wordBreakUtilTopDown(String s,
List<String> wordDict,
int index,
int[] table) {

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

if(table[index] < 0) {
boolean isBreakable = false;
for (int i = index; i < s.length(); i++) {
isBreakable = isBreakable
|| wordDict.contains(s.substring(index, i + 1))
&& wordBreakUtilTopDown(s, wordDict, i + 1);
}
table[index] = isBreakable ? 1 : 0;
}
return table[index] == 1 ? true : false;
}
}

```

If you run the first solution, it will exceed the time limit on leetcode, however, the second implementation should be accepted with 4ms as the time to run. Now you can appreciate the efficiency by memoization.

### Word break problem using dynamic programming

In the last two implementations, two things are evident: first, the optimal solution of a subproblem leads to the optimal solution of the original problem. Second, there are overlapping subproblems. These are two must have conditions for applying dynamic programming. We already saw the memoization and top-down approach of DP to avoid repeated solving of subproblems. How can we do it bottom up?

What if store an information if the string till index i is breakable? What will be the base case? The string before index 0 is alway breakable as empty string. So table can be always true. To check if string till index i is breakable or not, we check from index 0 to index i-1 if there is any index j till which string is breakable. If yes, then we just check if substring from index j to i, that will make `table[i]` as true.

```package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

public boolean wordBreak(String s, List<String> wordDict) {
return wordBreakBottomUp(s, wordDict, 0, table);
}

private boolean wordBreakUtilBottomUp(String s, List<String> wordDict){

if(s == null || s.length() == 0) return false;

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

table = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = i - 1; j >= 0; j--) {
if (table[j] && wordDict.contains(s.substring(j, i))) {
table[i] = true;
}
}
}
}
return table[s.length()];
}
}
```

The time complexity of the above implementation of the word break problem is `O(n2)`

If you want to store all the strings which can be generated by breaking a particular word, below is the code.

```package AlgorithmsAndMe;

import java.util.*;

public class WordBreak2 {

public List<String> wordBreak(String s, List<String> wordDict) {
Map<String, List<String>> map = new HashMap<>();
return wordBreakUtil2(s, wordDict, map);
}

private List<String> wordBreakUtil2(String s,
List<String> wordDict,
Map<String, List<String>> map) {

if(map.containsKey(s)){
return map.get(s);
}

List<String> result = new ArrayList<String>();
if (wordDict.contains(s)){
result.add(s);
}

for(int i=1; i<=s.length(); i++) {
String prefix = s.substring(0, i);
if(wordDict.contains(prefix)){
List<String> returnStringsList = wordBreakUtil2(s.substring(i), wordDict, map);

for(String returnString :returnStringsList ){
result.add(prefix + " " + returnString);
}
}
}
map.put(s,result);

return result;
}
}

```

Please share if there is something is wrong or missing. If you are preparing for an interview and need any help with preparation, please reach out to us or book a free session.

Posted on Leave a comment on Word break problem