2020 July 11 Problems

Daryl Wang

unread,

Jul 11, 2020, 12:54:13 PM7/11/20

to leetcode-meetup

Please work on the problems at home and post your solutions to the thread. I'll be discussing the questions next week.

198

House Robber

41.9%

Easy

213

House Robber II

36.3%

Medium

403

Frog Jump

39.5%

Hard

rajat aggarwal

unread,

Jul 11, 2020, 4:36:00 PM7/11/20

to leetcod...@googlegroups.com

198

House Robber

41.9%

Easy

class Solution {
public int rob(int[] nums) {
// solution using DP problem
if(nums.length==0)
{
return 0;
}

if(nums.length ==1)
{
return nums[0];
}

int dp[]=new int[nums.length+1];

dp[0]=0;
dp[1]=nums[0];
for(int i=2; i< dp.length; i++)
{

dp[i]= Math.max(nums[i-1] + dp[i-2], dp[i-1]);

}

return dp[dp.length-1];
}
}

--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS

https://www.techbayarea.us/

FB: https://www.facebook.com/techbayarea.us
Discord: https://discord.gg/yWMWptS
meetup : https://www.meetup.com/techbayarea/
google groups: https://groups.google.com/forum/#!forum/leetcode-meetup
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/5b610469-5b39-44f0-965f-40fecaa4db17o%40googlegroups.com.

rajat aggarwal

unread,

Jul 11, 2020, 5:03:18 PM7/11/20

to leetcod...@googlegroups.com

213

House Robber II

36.3%

Medium

public int rob(int[] nums) {
// Using dp, First iteration from i to n-2;
// second iteration i+1 to n
//. Return the max from last index
if(nums.length == 0)
{
return 0;
}

if(nums.length==1)
{
return nums[0];
}

if(nums.length==2)
{
return Math.max(nums[0], nums[1]);
}

int dp[]= new int[nums.length];
int dp2[]= new int [nums.length];

// first loop from 0 to dp.length

dp[0]=0;
dp[1]=nums[0];

for(int i=2; i< dp.length; i++)
{

dp[i]= Math.max(dp[i-2] + nums[i-1], dp[i-1]);

}

// second loop from 1 to dp.length
dp2[0]=0;
dp2[1]=nums[1];

for(int i=2; i< dp2.length; i++)
{

dp2[i]= Math.max(dp2[i-2] + nums[i], dp2[i-1]);

}

return Math.max(dp[dp.length-1], dp2[dp2.length-1]);
}

On Sat, Jul 11, 2020 at 9:54 AM Daryl Wang <daryl...@gmail.com> wrote:

--

rakesh katkam

unread,

Jul 11, 2020, 5:26:59 PM7/11/20

to leetcode-meetup

def rob(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

if len(nums) == 0:

return 0

if len(nums) == 1:

return nums[0]

if len(nums) == 2:

return max(nums[0],nums[1])

dp = [0]*(len(nums))

dp[0] = nums[0]

dp[1] = max(nums[0],nums[1])

i = 2

while i < len(nums):

dp[i] = max(nums[i] + dp[i-2],dp[i-1])

i += 1

return dp[len(nums)-1]

rakesh katkam

unread,

Jul 11, 2020, 5:28:35 PM7/11/20

to leetcode-meetup

def rob(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

if len(nums) == 0:

return 0

if len(nums) == 1:

return nums[0]

if len(nums) == 2:

return max(nums[0],nums[1])

return max(self.calculateSum(nums[:-1]),self.calculateSum(nums[1:]))

def calculateSum(self, nums):

dp = [0]*(len(nums))

dp[0] = nums[0]

dp[1] = max(nums[0],nums[1])

i = 2

while i < len(nums):

dp[i] = max(nums[i] + dp[i-2],dp[i-1])

i += 1

print(dp)

return dp[-1]

rajat aggarwal

unread,

Jul 11, 2020, 6:55:43 PM7/11/20

to leetcod...@googlegroups.com

403

Frog Jump

39.5%

Hard

public boolean canCross(int[] stones) {

// creating map of value and index then call the recursion to check all the position
HashSet<Integer> set= new HashSet<>();
HashMap<String, Boolean> memo=new HashMap<>();

for(int i=0; i< stones.length; i++)
{
set.add(stones[i]);
}

return dfs(0, stones, stones[0], set,memo);

}

private boolean dfs(int jump, int[] arr, int val, HashSet<Integer> set, HashMap<String, Boolean> memo)
{

if(val == arr[arr.length-1])
{
return true;
}

if(val > arr[arr.length-1])
{
return false;
}
// three call for all three option which is k-1, k, k+1
// do not call if k <=0

String ky= ""+val+"_"+jump;
if(memo.containsKey(ky))
{
boolean flg=(boolean)memo.get(ky);
return flg;
}

int less=jump-1;
int same=jump;
int greater=jump+1;

boolean f=false;
boolean s=false;
boolean t=false;

if(less >0 && set.contains(val+less))
{
f=dfs(less, arr, val+less, set, memo);
ky= (val+less)+"_"+less;
memo.put(ky, f);
}

if(same > 0 && set.contains(val+same))
{
s= dfs(same, arr, val+same, set, memo);
ky= (val+same)+"_"+same;
memo.put(ky, s);
}

if(set.contains(val+greater))
{
t=dfs(greater, arr, val+greater, set, memo);
ky= (val+greater)+"_"+greater;
memo.put(ky, t);
}

return f || s|| t;
}

On Sat, Jul 11, 2020 at 9:54 AM Daryl Wang <daryl...@gmail.com> wrote:

--

karan alang

unread,

Jul 12, 2020, 10:29:44 PM7/12/20

to leetcode-meetup

lc198 :

def rob(self, nums: List[int]) -> int:

if not nums:

return 0

dp = [0]*(len(nums)+1)

dp[1] = nums[0]

for i in range(2, len(nums)+1):

dp[i] = max(nums[i-1]+dp[i-2], dp[i-1])

return dp[-1]

karan alang

unread,

Jul 13, 2020, 2:11:39 AM7/13/20

to leetcode-meetup

lc213:

def rob(self, nums: List[int]) -> int:

if not nums:

return 0

if len(nums) == 1:

return nums[0]

def getMaxMoney(nums1):

dp = [0]*(len(nums1)+1)

dp[1]=nums1[0]

for i in range(2,len(nums1)+1):

dp[i] = max(nums1[i-1]+dp[i-2], dp[i-1])

# print(" dp -> ", dp)

return dp[-1]

one = getMaxMoney(nums[:len(nums)-1])

two = getMaxMoney(nums[1:len(nums)])

return max(one, two)

Abhishek Kaukuntla

unread,

Jul 14, 2020, 12:11:31 AM7/14/20

to leetcode-meetup

213

House Robber II

36.3%

Medium

class Solution {

/*

Strategy:

The houses are lined up in circle. The first and the last house are neighbors and we can rob only 1 of them.

Pass 1: Exclude the last house, rob the houses for max money.

Pass 2: Exclude the first house, rob the houses for max money.

At this point you know if you need to rob the first house or the last. Whatever the max amount you robbed is the answer.

Runtime: 0 ms, faster than 100.00% of Java online submissions for House Robber II.

Memory Usage: 36.9 MB, less than 53.15% of Java online submissions for House Robber II.

Time complexity: O(N)

Space complexity: O(1)

*/

public int rob(int[] nums) {

int a=0, b=0, len = nums.length;

if (len == 1) {

return nums[0];

}

a = robHelper(nums, 0, len-1);

b = robHelper(nums, 1, len);

return Math.max(a, b);

}

private int robHelper(int[] nums, int start, int end) {

int a=0, b=0;

for (int i=start; i<end; i++) {

if (i%2 == 0) {

a = Math.max(a + nums[i], b);

} else {

b = Math.max(a, b + nums[i]);

}

return Math.max(a, b);

}

On Saturday, July 11, 2020 at 9:54:13 AM UTC-7, Daryl Wang wrote:

Abhishek Kaukuntla

unread,

Jul 15, 2020, 12:36:59 AM7/15/20

to leetcode-meetup

403

Frog Jump

39.5%

Hard

class Solution {

/*

Date: 07/14/2020

Strategy: Dynamic programming

Use a 2D boolean array to store the possible jump units at every stone. The rows represent the stones and the column represents the jump units possible at each stone.

For current stone we check if it can be reached from every previous stone. If yes, then we set the (jump-1), (jump), (jump+1) columns to true for the current stone. Repeat this for all the stones.

When we reach the last stone, if it can be reached from any of the previous stone, we reached the end successfully. Return true. Otherwise, false.

Runtime: 24 ms, faster than 75.45% of Java online submissions for Frog Jump.

Memory Usage: 43.5 MB, less than 63.29% of Java online submissions for Frog Jump.

Time complexity: O(N^2)

Space complexity: O(N^2)

*/

public boolean canCross(int[] stones) {

int len = stones.length;

if (len <= 1) {

return true;

}

int N = stones.length;

// The rows represent the stones and the columns represent the jumps that can be taken at this stone

boolean[][] dp = new boolean[N][N];

// Because we take 1 jump at first stone

dp[0][1] = true;

// For each stone, we check if we can reach to it from any of the previous stones

for (int i=1; i<N; i++) { // i represents the current stone

for (int j=0; j<i; j++) { // j represent the previous stones

int dist = stones[i] - stones[j];

// if distance is out of boundary or if we cannot reach the current stone from the previous stone

if (dist < 0 || dist > N-1 || !dp[j][dist]) {

continue;

}

if (dp[j][dist]) { // we can reach the current stone i from the stone j at a distance dist. If the current stone is the last stone, then we reached the end. Return true.

if (i == N-1) {

return true;

}

dp[i][dist-1] = dp[i][dist] = dp[i][dist+1] = true; // set the possible jumps that can be taken at current stone to true

}

return false;

}

On Saturday, July 11, 2020 at 9:54:13 AM UTC-7, Daryl Wang wrote:

Daryl Wang

unread,

Jul 17, 2020, 10:52:09 PM7/17/20

to leetcode-meetup

198

House Robber

41.9%

Easy

The basic idea is that at the ith house, we have two choices to maximize the profit from the first i houses:

1) Rob the ith house, and rob the best combination of the first i - 2 houses.

2) Skip the ith house, and rob the best combination of the first i - 1 houses.

The base cases are i=1 and i=2:

i=1) Rob the first house

i=2) Rob the bigger of the first two houses

So we have broken the problem into two smaller subproblems and have a base case.

This can be implemented recursively or through dynamic programming. The code below is for the dynamic programming approach. The main data structure is an array that keeps the best profit from the first i houses at each position i. We can then fill in the first two elements with the bases cases discussed above, and the iterate i from there.

O(n) space

O(n) time

class Solution:

def rob(self, nums: List[int]) -> int:

if len(nums) < 2:

return max(nums) if nums else 0

dp = [nums[0], max(nums[:2])]

for i, num in enumerate(nums[2:]):

i += 2

dp.append(max(dp[i - 1], num + dp[i - 2]))

return max(dp)

On Saturday, July 11, 2020 at 9:54:13 AM UTC-7, Daryl Wang wrote:

Daryl Wang

unread,

Jul 17, 2020, 11:08:40 PM7/17/20

to leetcode-meetup

213

House Robber II

36.3%

Medium

The simplest way to deal with the ring of houses is to break it into two chains of houses:

1) One chain where the first house is left out.

2) One chain where the last house is left out.

This way we don't have to worry about choosing both the first and last house, since neither chain has both. We can then just use the House Robber I solution to calculate the profits from robbing both of these chains, and return the bigger result.

O(n) time

O(n) space

class Solution:

def rob(self, nums: List[int]) -> int:

if len(nums) < 3:

return max(nums) if nums else 0

def houseRobber1(nums):

if len(nums) < 2:

return max(nums) if nums else 0

dp = [nums[0], max(nums[:2])]

for i, num in enumerate(nums[2:]):

i += 2

dp.append(max(dp[i - 1], num + dp[i - 2]))

return max(dp)

return max(houseRobber1(nums[1:]), houseRobber1(nums[:-1]))

On Saturday, July 11, 2020 at 9:54:13 AM UTC-7, Daryl Wang wrote:

Daryl Wang

unread,

Jul 17, 2020, 11:49:23 PM7/17/20

to leetcode-meetup

403

Frog Jump

39.5%

Hard

There are several ways to approach this problem. The code I've provided is for the DFS approach, but a dynamic programming approach is also possible.

With DFS this problem is relatively straightforward. We maintain a list of possible (position, K) pairs, which represents the frog's current position and last K size. We take one of these (position, K) pairs and then see where the frog can reach. There are three possible new positions: position + K - 1, position + K, position + K + 1. If a stone exists at the new position, then we add it and the K value used as a pair to the list of pairs. We repeat the process until we reach the end or have run out of possible (position, K) pairs to jump from. To avoid repeating work we'll keep a set of (position, K) pairs we've already reached so we don't repeat work.

Alternatively, we can do this through dynamic programming. Our DP array is a N * N square array of booleans, where N is the number of stones + 1. dp[i][j] is True if it is possible to make a jump of size j from position i, false otherwise. We make the same considerations as before for each i,j pair: there are three possible new pairs of (i + j - 1, j - 1), (i + j, j), and (i + j + 1, j + 1). We start off with [0][1] as True, and from there iterate on stones until we hit the final stone and see if any of the values there are true.

0 1 3 4 6 positions

0 F T F F F

1 T T F T F

2 F T T F T

3 F F F F T

K values

O(n^2) time

O(n^2) space

class Solution:

def canCross(self, stones: List[int]) -> bool:

if len(stones) < 2:

return True

moves = []

# If second stone isn't at position 1 the frog is immediately stuck

if stones[1] == 1:

moves.append((1,1))

stonesSet = set(stones)

seenMoves = set()

end = stones[-1]

while moves:

stone, k = moves.pop()

if stone == end:

return True

for newK in range(max(1, k - 1), k + 2):

newStone = (stone + newK)

newMove = (newStone, newK)

if newStone in stonesSet and newMove not in seenMoves:

moves.append(newMove)

seenMoves.add(newMove)

return False

On Saturday, July 11, 2020 at 9:54:13 AM UTC-7, Daryl Wang wrote:

Reply all

Reply to author

Forward