LeetCode [740] Delete and Earn

 740. Delete and Earn

Medium

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

Input: nums = [3, 4, 2]
Output: 6
Explanation: 
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.

 

Example 2:

Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.

 

Note:

• The length of nums is at most 20000.
• Each element nums[i] is an integer in the range [1, 10000].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { /* p2 p1 p0 p2 p1 */ public int deleteAndEarn(int[] nums) { int n = 10001; int[] sum = new int[n]; int max = 0; for(int i : nums) sum[i] += i; int p1 = 0, p2 = 0; for(int i=0; i<n; ++i){ //max earned point until current position int p0 = Math.max(sum[i]+p2, p1); p2 = Math.max(p1, p2); p1 = p0; max = Math.max(max, p0); } return max; } }

LeetCode [1697] Checking Existence of Edge Length Limited Paths

 1697. Checking Existence of Edge Length Limited Paths

Hard

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes.

Given an array queries, where queries[j] = [pj, qj, limitj], your task is to determine for each queries[j] whether there is a path between pj and qj such that each edge on the path has a distance strictly less than limitj .

Return a boolean array answer, where answer.length == queries.length and the jth value of answer is true if there is a path for queries[j] is true, and false otherwise.

 

Example 1:

Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
Output: [false,true]
Explanation: The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.
For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query.
For the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.

Example 2:

Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
Output: [true,false]
Exaplanation: The above figure shows the given graph.

 

Constraints:

• 2 <= n <= 105
• 1 <= edgeList.length, queries.length <= 105
• edgeList[i].length == 3
• queries[j].length == 3
• 0 <= ui, vi, pj, qj <= n - 1
• ui != vi
• pj != qj
• 1 <= disi, limitj <= 109
• There may be multiple edges between two nodes.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

class Solution { public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) { int[] p = new int[n]; for(int i=0; i<n; ++i) p[i] = i; Arrays.sort(edgeList, (a, b) -> a[2]-b[2]); int szQ = queries.length; int szE = edgeList.length; boolean[] ret = new boolean[szQ]; int[][] queries1 = new int[szQ][4]; for(int i=0; i<szQ; ++i){ queries1[i][0] = queries[i][0]; queries1[i][1] = queries[i][1]; queries1[i][2] = queries[i][2]; queries1[i][3] = i; } Arrays.sort(queries1, (a, b) -> a[2]-b[2]); int idQ = 0; int idE = 0; while(idQ < szQ){ int limit = queries1[idQ][2]; while(idE < szE && edgeList[idE][2]<limit){ int u = edgeList[idE][0]; int v = edgeList[idE][1]; int x = find(u, p); int y = find(v, p); p[y] = x; idE++; } int p1 = find(queries1[idQ][0], p); int p2 = find(queries1[idQ][1], p); ret[queries1[idQ][3]] = p1==p2; idQ++; } return ret; } int find(int x, int[] p){ while(x!=p[x]) return find(p[x], p); return x; } }

LeetCode [1616] Split Two Strings to Make Palindrome

 1616. Split Two Strings to Make Palindrome

Medium

You are given two strings a and b of the same length. Choose an index and split both strings at the same index, splitting a into two strings: aprefix and asuffix where a = aprefix + asuffix, and splitting b into two strings: bprefix and bsuffix where b = bprefix + bsuffix. Check if aprefix + bsuffix or bprefix + asuffix forms a palindrome.

When you split a string s into sprefix and ssuffix, either ssuffix or sprefix is allowed to be empty. For example, if s = "abc", then "" + "abc", "a" + "bc", "ab" + "c" , and "abc" + "" are valid splits.

Return true if it is possible to form a palindrome string, otherwise return false.

Notice that x + y denotes the concatenation of strings x and y.

 

Example 1:

Input: a = "x", b = "y"
Output: true
Explaination: If either a or b are palindromes the answer is true since you can split in the following way:
aprefix = "", asuffix = "x"
bprefix = "", bsuffix = "y"
Then, aprefix + bsuffix = "" + "y" = "y", which is a palindrome.

Example 2:

Input: a = "abdef", b = "fecab"
Output: true

Example 3:

Input: a = "ulacfd", b = "jizalu"
Output: true
Explaination: Split them at index 3:
aprefix = "ula", asuffix = "cfd"
bprefix = "jiz", bsuffix = "alu"
Then, aprefix + bsuffix = "ula" + "alu" = "ulaalu", which is a palindrome.

Example 4:

Input: a = "xbdef", b = "xecab"
Output: false

 

Constraints:

• 1 <= a.length, b.length <= 105
• a.length == b.length
• a and b consist of lowercase English letters

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public boolean checkPalindromeFormation(String a, String b) { if(helper(a, b, 0, b.length()-1, false)) return true; return helper(b, a, 0, a.length()-1, false); } boolean helper(String a, String b, int l, int r, boolean oneString){ if(l>=r) return true; if(a.charAt(l)!=b.charAt(r)) return false; if(helper(a, b, l+1, r-1, oneString)) return true; if(!oneString){ if(helper(a, a, l+1, r-1, true)) return true; if(helper(b, b, l+1, r-1, true)) return true; } return false; } }

LeetCode [1642] Furthest Building You Can Reach

 1642. Furthest Building You Can Reach

Medium

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

• If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.
• If the current building's height is less than the next building's height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

 

Example 1:

Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.

Example 2:

Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7

Example 3:

Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3

 

Constraints:

• 1 <= heights.length <= 105
• 1 <= heights[i] <= 106
• 0 <= bricks <= 109
• 0 <= ladders <= heights.length

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public int furthestBuilding(int[] heights, int bricks, int ladders) { PriorityQueue<Integer> pq = new PriorityQueue<>(); int i = 0; while(i<heights.length-1){ int diff = heights[i+1]-heights[i]; if(diff>0){ pq.add(diff); if(pq.size()>ladders){ bricks -= pq.poll(); if(bricks<0) return i; } } i++; } return i; } }

LeetCode [1658] Minimum Operations to Reduce X to Zero

 1658. Minimum Operations to Reduce X to Zero

Medium

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it's possible, otherwise, return -1.

 

Example 1:

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104
• 1 <= x <= 109

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public int minOperations(int[] nums, int x) { int target = 0; for(int i : nums) target += i; target -= x; int n = nums.length; if(target==0) return n; Map<Integer, Integer> map = new HashMap<>(); map.put(0, -1); int sum = 0; int maxLen = -1; for(int i=0; i<n; ++i){ sum += nums[i]; int diff = sum-target; if(map.containsKey(diff)){ int len = i-map.get(diff); maxLen = Math.max(maxLen, len); } if(!map.containsKey(sum)) map.put(sum, i); } return maxLen==-1?-1:n-maxLen; } }