LeetCode daily problems

Contents

2831. Find the Longest Equal Subarray 🟠 05-23-2024

Description:

You are given a 0-indexed integer array nums and an integer k.

A subarray is called equal if all of its elements are equal. Note that the empty subarray is an equal subarray.

Return the length of the longest possible equal subarray after deleting at most k elements from nums.

A subarray is a contiguous, possibly empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,3,2,3,1,3], k = 3
Output: 3
Explanation: It's optimal to delete the elements at index 2 and index 4.
After deleting them, nums becomes equal to [1, 3, 3, 3].
The longest equal subarray starts at i = 1 and ends at j = 3 with length equal to 3.
It can be proven that no longer equal subarrays can be created.

Example 2:

Input: nums = [1,1,2,2,1,1], k = 2
Output: 4
Explanation: It's optimal to delete the elements at index 2 and index 3.
After deleting them, nums becomes equal to [1, 1, 1, 1].
The array itself is an equal subarray, so the answer is 4.
It can be proven that no longer equal subarrays can be created.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= nums.length
  • 0 <= k <= nums.length

Ideas After analyze we find for each element with same value, we can use sliding window to calculate the max num that meet the constraints. So basically for each distinct value, we need a sliding window.

  1. traverse the array get the map, then for each key in map, do a sliding window
0 1 2 3 4 5 6
1 3 2 3 1 3 1 k = 3
i
            j

map<value, list of index>
map: {
    1 : 0 4 6
    3 : 1 3 5
    2 : 2
}

we can use list to store index, and use two int stand for the boundary. or a simple way -> use queue.pop to update the boundary.

  1. We find the above solution need traverse the array two times in total. Is there a simple way to calculate while traversing the array?

In a queue, how to determine if new added element is satisfied? answer is : (index - queue.peekFirst() + 1) - queue.size() > k ? (index - queue.peekFirst() + 1) stand for the length between the first and last occurance of the element. To calculate the rest number of elements who’s value are not euqlas to the current value, we use length - number of current value in between, compare it with the k. if greater than k, that means it can not be replaced within k times. then we need to pop the first element out of the queue and check again until it is satisfied. Then we update the globalmax.

Solution

class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int globalMax = Integer.MIN_VALUE;
        Map<Integer, Deque<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.size(); i++) {
            // add it to the map
            Deque<Integer> queue = map.computeIfAbsent(nums.get(i), num -> new ArrayDeque<>());
            queue.offerLast(i);
            // update the boundary
            while(i - queue.peekFirst() + 1 - queue.size() > k) {
                queue.pollFirst();
            }
            globalMax = Math.max(globalMax, queue.size());
        }
        return globalMax;
    }
}

447. Number of Boomerangs 🟠 01-08-2024

447. Number of Boomerangs

Description:

You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. A boomerang is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Return the number of boomerangs.

 

Example 1:

Input: points = [[0,0],[1,0],[2,0]]
Output: 2
Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]].

Example 2:

Input: points = [[1,1],[2,2],[3,3]]
Output: 2

Example 3:

Input: points = [[1,1]]
Output: 0

 

Constraints:

  • n == points.length
  • 1 <= n <= 500
  • points[i].length == 2
  • -104 <= xi, yi <= 104
  • All the points are unique.

Ideas:

When we first see this problem, we can easily come up with a brute force solution. We can use three for loops to find the boomerangs. But the time complexity will be O(n^3).

Another way to solve this problem is : for each point, use a hashmap to store the distance between this point and other points. Then we know how many points have the same distance to this point.

For point A, if there exists n points have the same distance to A, that means we can pick any two of n points to form a boomerang. So the total number of boomerangs is n * (n - 1).

With this idea, we can for loop the entryset of the map and calculate the total number of boomerangs of one point and sum of all points.

Solution:

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if (points.length < 3) return 0;
        int res = 0;
        // for each point, calculate the distance between this point and other points
        for (int[] p : points) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int[] q : points) {
                int dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
                map.put(dis, map.getOrDefault(dis, 0) + 1);
            }
            // for each point, calculate the total number of boomerangs
            for (Map.Entry<Integer, Integer> e : map.entrySet()) {
                int m = e.getValue();
                res += m * (m - 1);
            }
        }
        return res;
    }
}

356. Line Reflection 🟠 01-08-2024

356. Line Reflection

Description:

Given n points on a 2D plane, find if there is such a line parallel to the y-axis that reflects the given points symmetrically.

In other words, answer whether or not if there exists a line that after reflecting all points over the given line, the original points' set is the same as the reflected ones.

Note that there can be repeated points.

 

Example 1:

Input: points = [[1,1],[-1,1]]
Output: true
Explanation: We can choose the line x = 0.

Example 2:

Input: points = [[1,1],[-1,-1]]
Output: false
Explanation: We can't choose a line.

 

Constraints:

  • n == points.length
  • 1 <= n <= 104
  • -108 <= points[i][j] <= 108

 

Follow up: Could you do better than O(n2)?

Ideas:

Since we only reflect Y axis, to find the line, we can easily get the line with the leftmost and rightmost points. Then we can use a hashset to store the points. Then we can check if the reflected points are in the hashset.

Solution:

class Solution {

    // Here we create a new class Point to store the x and y value, and override the equals and hashCode method
    class Point {
        double x;
        double y;
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true; // check reference
            // check null and class type
            if (o == null || getClass() != o.getClass()) return false;
            // cast o to Point
            Point point = (Point) o;
            return point.x == this.x && point.y == this.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

    }

    public boolean isReflected(int[][] points) {
        if (points.length == 1) return true;
        Set<Point> pointSet = new HashSet<>();
        double min = Integer.MAX_VALUE;
        double max = Integer.MIN_VALUE;
        for (int[] point : points) {
            max = Math.max(point[0], max);
            min = Math.min(point[0], min);
            pointSet.add(new Point(point[0], point[1]));
        }
        // Here 2 * (line - point[0]) + point[0] is the reflected point, we don't need to consider the point is at the left or right of the line
        double line = min + (max - min) / 2;
        for (int[] point : points) {
            if (!pointSet.contains(new Point(2 * (line - point[0]) + point[0], point[1])))  return false;
        }
        return true;
    }
}

146. LRU Cache 🟠 01-07-2024

146. LRU Cache

Description:

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

 

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

 

Constraints:

  • 1 <= capacity <= 3000
  • 0 <= key <= 104
  • 0 <= value <= 105
  • At most 2 * 105 calls will be made to get and put.

Ideas:

  1. We can use a Doubly Linked List to store the key and value. Head -> A -> B -> C -> D -> Tail With this we can easily remove the tail and add a new node to the head. But the problem is to find the node in the list. We can use a HashMap to store the key and the node. So we can easily find the node in the list. HashMap: key -> Node. So the time complexity for get and put is O(1).
class LRUCache {

    class DoubledListNode {
    int key;
    int value;
    DoubledListNode prev;
    DoubledListNode next;
    DoubledListNode(int key, int value) {
        this.key = key;
        this.value = value;
        }
    }

    // initialize the cache
    Map<Integer, DoubledListNode> cache = new HashMap<>();
    int capacity;
    int size;
    DoubledListNode head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.head = new DoubledListNode(-1, -1);
        this.tail = new DoubledListNode(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {

    }

    public void put(int key, int value) {

    }
}
  1. With the structure above, we can focus on the get and put method.
    public int get(int key) {
        // if the key is not in the cache, return -1
        // if the key is in the cache, return the value and move the node to the head

        // summary : we need a method moveToHead(DoubledListNode node)
        // for this method, it contains two steps:
        // 1. remove the node from the list -> removeNode(node)
        // 2. add the node to the head  -> addNewNodeToHead(node)
    }

    public void put(int key, int value) {
        // if the key is in the cache, update the value and move the node to the head
        // if the key is not in the cache, add the node to the head, if the size is greater than capacity, remove the tail

        // summary : we need a method moveToHead(DoubledListNode node) and addNewNodeToHead(DoubledListNode node) and evictTail()

    }
  1. Implement the methods above
    private void moveToHead(DoubledListNode node) {
        // remove the node from the list
        removeNode(node);
        // add the node to the head
        addNewNodeToHead(node);
    }

    private void removeNode(DoubledListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addNewNodeToHead(DoubledListNode node) {
        node.next = head.next;
        node.prev = head;
        // remember to update the head and the previous node next to head
        head.next.prev = node;
        head.next = node;
    }

    private void evictTail() {
        DoubledListNode tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;
    }


  1. Implement the Get and Put methods
    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        DoubledListNode node = cache.get(key);
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            DoubledListNode node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            DoubledListNode node = new DoubledListNode(key, value);
            cache.put(key, node);
            addNewNodeToHead(node);
            size++;
            if (size > capacity) {
                DoubledListNode tailNode = evictTail();
                cache.remove(tailNode.key);
                size--;
            }
        }
    }
  1. the final solution
class LRUCache {

    class DoubledListNode {
        int key;
        int value;
        DoubledListNode prev;
        DoubledListNode next;
        DoubledListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    Map<Integer, DoubledListNode> cache = new HashMap<>();
    int capacity;
    int size;
    DoubledListNode head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.head = new DoubledListNode(-1, -1);
        this.tail = new DoubledListNode(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DoubledListNode node = cache.get(key);
        // not exist -> return -1
        if (node == null) return -1;
        // exist, move node to head, return value;
        moveToHead(node);
        return node.value;
    }

        public void put(int key, int value) {
        // if exist, update value, move to head
        DoubledListNode node = cache.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
        } else {
            DoubledListNode newNode = new DoubledListNode(key, value);
            cache.put(key, newNode);
            addNewNodeToHead(newNode);
            size++;
            if (size > capacity) {
                DoubledListNode tailNode = evictTail();
                this.size--;
                cache.remove(tailNode.key);
            }
        }
        // not exist, add a new node to head (update map), check if exceed capacity? evict tail node
    }

    private void moveToHead(DoubledListNode node) {
        // break current node prev and next
        removeNode(node);
        // move to head
        addNewNodeToHead(node);
    }

    private void addNewNodeToHead(DoubledListNode node) {
        node.prev = head;
        node.next = head.next;
        // **
        head.next.prev = node;
        head.next = node;
    }

    private DoubledListNode evictTail() {
        DoubledListNode tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;
    }
    private void removeNode(DoubledListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

2558. Take Gifts From the Richest Pile 🟢 10-26-2023

2558. Take Gifts From the Richest Pile

Description:

You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following:

  • Choose the pile with the maximum number of gifts.
  • If there is more than one pile with the maximum number of gifts, choose any.
  • Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.

Return the number of gifts remaining after k seconds.

 

Example 1:

Input: gifts = [25,64,9,4,100], k = 4
Output: 29
Explanation: 
The gifts are taken in the following way:
- In the first second, the last pile is chosen and 10 gifts are left behind.
- Then the second pile is chosen and 8 gifts are left behind.
- After that the first pile is chosen and 5 gifts are left behind.
- Finally, the last pile is chosen again and 3 gifts are left behind.
The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.

Example 2:

Input: gifts = [1,1,1,1], k = 4
Output: 4
Explanation: 
In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile. 
That is, you can't take any pile with you. 
So, the total gifts remaining are 4.

 

Constraints:

  • 1 <= gifts.length <= 103
  • 1 <= gifts[i] <= 109
  • 1 <= k <= 103

Ideas: Each time, we need to pick the maximum of the array, and push the new value back to the array. So we can use a priority queue to solve this problem.

Solution:

class Solution {
    public long pickGifts(int[] gifts, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(gifts.length, (e1, e2) -> e2 - e1);
        pq.addAll(Arrays.stream(gifts).mapToObj(Integer::valueOf).collect(Collectors.toList()));
        // do not know addAll is heapify the array?
        while (k-- > 0) {
            pq.offer((int) Math.sqrt(pq.poll()));
        }
        long res = 0;
        while (!pq.isEmpty()) {
            res += pq.poll();
        }
        return res;
    }
}

Time complexity: O(n + klogn) where n is the length of the gifts array

Space complexity: O(n)

1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts 🟠 10-27-2023

1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Description:

You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where:

  • horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, and
  • verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 109 + 7.

 

Example 1:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2:

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.

Example 3:

Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9

 

Constraints:

  • 2 <= h, w <= 109
  • 1 <= horizontalCuts.length <= min(h - 1, 105)
  • 1 <= verticalCuts.length <= min(w - 1, 105)
  • 1 <= horizontalCuts[i] < h
  • 1 <= verticalCuts[i] < w
  • All the elements in horizontalCuts are distinct.
  • All the elements in verticalCuts are distinct.

Original Ideas:

The first idea I got is calculate the intervals for horizontal and vertical cuts. Then do a for loop to find the maximum area. But this solution is not efficient enough. The time complexity is O(n^2) where n is the length of the horizontalCuts or verticalCuts.

Ideas:

Based on the original ideas, we analyze the problem and find that we only need to find the maximum interval for horizontalCuts and verticalCuts. So we can sort the horizontalCuts and verticalCuts and find the maximum interval for horizontalCuts and verticalCuts. Then we can get the maximum area by multiply the maximum interval for horizontalCuts and verticalCuts.

Solution:

class Solution {
    private final int MOD = 100000007;
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        // here is another hard part, to convert long to int. For these problems that need mod 10e9 + 7, if we do not need time operation, we can use int, otherwise we need to use long
        return (int) (findMaxInterval(horizontalCuts, h) * findMaxInterval(verticalCuts, w) % 1000000007);
    }
    public long findMaxInterval(int[] array, int length){
        int res = 0, pre = 0;
        for (int i = 0; i < array.length; i++) {
            res = Math.max(array[i] - pre, res);
            pre = array[i];
        }
        return (long) Math.max(res, length - pre);
    }
}

Time complexity: O(nlogn) where n is the length of horizontalCuts or verticalCuts (sorting)

Space complexity: O(1)

2520. Count the Digits That Divide a Number 🟢 10-26-2023

2520. Count the Digits That Divide a Number

Description:

Given an integer num, return the number of digits in num that divide num.

An integer val divides nums if nums % val == 0.

 

Example 1:

Input: num = 7
Output: 1
Explanation: 7 divides itself, hence the answer is 1.

Example 2:

Input: num = 121
Output: 2
Explanation: 121 is divisible by 1, but not 2. Since 1 occurs twice as a digit, we return 2.

Example 3:

Input: num = 1248
Output: 4
Explanation: 1248 is divisible by all of its digits, hence the answer is 4.

 

Constraints:

  • 1 <= num <= 109
  • num does not contain 0 as one of its digits.

Ideas:

The best way to do it is using the modulo operation. If convert to String, the space complexity will be O(n) where n is the length of the string. If we use modulo operation, the space complexity will be O(1).

Solution:

class Solution {
    public int countDigits(int num) {
        int t = num;
        int res = 0;
        while (t != 0) {
            if (num % (t % 10) == 0) {
                res++;
            }
            t /= 10;
        }
        return res;
    }
}

Time complexity: O(logn) where n is the number.

Space complexity: O(1)

2698. Find the Punishment Number of an Integer 🟠 10-25-2023

2698. Find the Punishment Number of an Integer

Description:

Given a positive integer n, return the punishment number of n.

The punishment number of n is defined as the sum of the squares of all integers i such that:

  • 1 <= i <= n
  • The decimal representation of i * i can be partitioned into contiguous substrings such that the sum of the integer values of these substrings equals i.

 

Example 1:

Input: n = 10
Output: 182
Explanation: There are exactly 3 integers i that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1.
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0.
Hence, the punishment number of 10 is 1 + 81 + 100 = 182

Example 2:

Input: n = 37
Output: 1478
Explanation: There are exactly 4 integers i that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1. 
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1. 
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0. 
- 36 since 36 * 36 = 1296 and 1296 can be partitioned into 1 + 29 + 6.
Hence, the punishment number of 37 is 1 + 81 + 100 + 1296 = 1478

 

Constraints:

  • 1 <= n <= 1000

Ideas:

After we analyze the problem, we can find the hard part is to cut the number into contiguous substrings. To get different combination of numbers, we can use DFS to solve this.

Solution:

    public int punishmentNumber(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (canPartitioned(String.valueOf(i*i), i, 0, 0)) sum += i * i;
        }
        return sum;

    }
    public boolean canPartitioned(String num, int target, int index, int sum) {
        if (index == num.length()) {
            return sum == target;
        }
        // here we do not have the choice to pick nothing, so the index start from index + 1
        // add [index, i) substring to the sum
        for (int i = index + 1; i <= num.length(); i++) {
            // here we can do a early termination if the sum is greater than target
            if (canPartitioned(num, target, i, sum + Integer.parseInt(num.substring(index, i)))) return true;
        }
        return false;
    }

Time complexity: non-polynomial time complexity since DFS is used

Space complexity: O(n * len(i*i)) where n is the input and len(i*i) is the length of the square of i (the maximum length is 2 * len(n)), so the space complexity is O(n * len(n))

1155. Number of Dice Rolls With Target Sum 🟠 10-24-2023

1155. Number of Dice Rolls With Target Sum

Description:

You have n dice, and each die has k faces numbered from 1 to k.

Given three integers n, k, and target, return the number of possible ways (out of the kn total ways) to roll the dice, so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 109 + 7.

 

Example 1:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

Example 2:

Input: n = 2, k = 6, target = 7
Output: 6
Explanation: You throw two dice, each with 6 faces.
There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:

Input: n = 30, k = 30, target = 500
Output: 222616187
Explanation: The answer must be returned modulo 109 + 7.

 

Constraints:

  • 1 <= n, k <= 30
  • 1 <= target <= 1000

Ideas: We can use dynamic programming to solve this problem. DP[n][t] represents the number of possible ways to roll n dices, so the sum of the face-up numbers equals t.

We have the transition function:

DP[n][t] = ∑ (DP[n - 1][t - j]) where j is from 1 to k && t - j >= 0

Solution:

class Solution {
    private static final int MOD = 1000000007;
    public int numRollsToTarget(int n, int k, int target) {
        int[][] DP = new int[n + 1][target + 1];
        // min of k and target (corner case will cause index out of bound)
        int min = k > target ? target : k;
        // initilization the base case
        for (int i = 1; i <= min; i++) {
            DP[1][i] = 1;
        }
        // DP bottom up
        for (int i = 2; i < n + 1; i++) {
            // start with DP[i][i] because when t < i, it is impossible to roll i dices and get the sum of t
            for (int t = i; t < target + 1; t++) {
                for (int j = 1; j <= k; j++) {
                    if (t - j >= 0) DP[i][t] = (DP[i][t] + DP[i - 1][t - j]) % MOD;
                }
            }
        }
        return DP[n][target];
    }
}

Time complexity: O(n * k * target)

Space complexity: O(n * target)

2678. Number of Senior Citizens 🟢 10-23-2023

2678. Number of Senior Citizens

Description:

You are given a 0-indexed array of strings details. Each element of details provides information about a given passenger compressed into a string of length 15. The system is such that:

  • The first ten characters consist of the phone number of passengers.
  • The next character denotes the gender of the person.
  • The following two characters are used to indicate the age of the person.
  • The last two characters determine the seat allotted to that person.

Return the number of passengers who are strictly more than 60 years old.

 

Example 1:

Input: details = ["7868190130M7522","5303914400F9211","9273338290F4010"]
Output: 2
Explanation: The passengers at indices 0, 1, and 2 have ages 75, 92, and 40. Thus, there are 2 people who are over 60 years old.

Example 2:

Input: details = ["1313579440F2036","2921522980M5644"]
Output: 0
Explanation: None of the passengers are older than 60.

 

Constraints:

  • 1 <= details.length <= 100
  • details[i].length == 15
  • details[i] consists of digits from '0' to '9'.
  • details[i][10] is either 'M' or 'F' or 'O'.
  • The phone numbers and seat numbers of the passengers are distinct.

Ideas:

This is a simple problem, the only thing we need to do is to extract the age from the string and compare it with 60.

Solution:

class Solution {
    public int numOlderThan60(String[] details) {
        int res = 0;
        for (String detail : details) {
        // extract the age from the string using substring, instead of using character and ascii code to manually calculate the age like this : Integer.valueOf(str.charAt(11) - '0') * 10 + Integer.valueOf(str.charAt(12) - '0');
            int age = Integer.parseInt(detail.substring(10, 12));
            if (age > 60) res++;
            // or we can only compare the 11th character with '6' to check if the age is greater than 60
        }
        return res;
    }
}
Class Solution {
    // using Stream API only for Java 8 and above
    public int numOlderThan60(String[] details) {
        return (int)Arrays.stream(details).filter(string -> Integer.valueOf(string.substring(11,13)) > 60).count();
    }
}

Time complexity: O(n)

Space complexity: O(1)

1402. Reducing Dishes 🔴 10-22-2023

1402. Reducing Dishes

Description:

A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.

Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i] * satisfaction[i].

Return the maximum sum of like-time coefficient that the chef can obtain after preparing some amount of dishes.

Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

 

Example 1:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

Example 2:

Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)

Example 3:

Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People do not like the dishes. No dish is prepared.

 

Constraints:

  • n == satisfaction.length
  • 1 <= n <= 500
  • -1000 <= satisfaction[i] <= 1000

Ideas:

The intuition behind this approach is that we always try to maximize the like-time coefficient by prioritizing dishes with higher satisfaction.

To get the maximum like-time coefficient, apparently all non-negative satisfaction dishes should be included. The rest is how to deal with negative satisfaction dishes.

First we sort the array in ascending order and iterate from back to front. [-9, -8, -1, 0, 5] when it comes to -1, now the dishes we pick is [0, 5] and the sum is 5, each time we add a new dishes, the satisfaction level will increase by sum of all previous selected dishes and the current dishes (here is - 1 + 0 + 5 = 4) which is sum + satisfaction[i]. if sum + satisfaction[i] is less than 0, we can stop the iteration because the rest dishes will be less than 0. If sum + satisfaction[i] is greater than 0, we can add it to the result.

To record the result, we can use a variable res to record the result, each time we pick a new dishes, the result will increase sum + satisfaction[i]. We don’t need to record the list of the dishes and calculate the sum by times[i] * satisfaction[i].

Solution:

We can use a greedy approach. We start by sorting the satisfaction array in descending order. Then, we iterate over the array and keep accumulating the satisfaction until the accumulated value is greater than zero. At each step, we update our result.

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        int sum = 0;
        int res = 0;
        Arrays.sort(satisfaction);
        for (int i = satisfaction.length - 1; i >= 0; i--) {
            if (satisfaction[i] < 0 && sum + satisfaction[i] < 0) break;
            sum += satisfaction[i--];
            res += sum;
        }
        return res;
    }
}

Time complexity: O(nlogn)

Space complexity: O(1)

3254. Find the Power of K-Size Subarrays I 🟢 11-08-2024

You are given an array of integers nums of length n and a positive integer k.

The power of an array is defined as:

  • Its maximum element if all of its elements are consecutive and sorted in ascending order.
  • -1 otherwise.

You need to find the power of all

of nums of size k.

Return an integer array results of size n - k + 1, where results[i] is the power of nums[i..(i + k - 1)].

 

Example 1:

Input: nums = [1,2,3,4,3,2,5], k = 3

Output: [3,4,-1,-1,-1]

Explanation:

There are 5 subarrays of nums of size 3:

  • [1, 2, 3] with the maximum element 3.
  • [2, 3, 4] with the maximum element 4.
  • [3, 4, 3] whose elements are not consecutive.
  • [4, 3, 2] whose elements are not sorted.
  • [3, 2, 5] whose elements are not consecutive.

Example 2:

Input: nums = [2,2,2,2,2], k = 4

Output: [-1,-1]

Example 3:

Input: nums = [3,2,3,2,3,2], k = 2

Output: [-1,3,-1,3,-1]

 

Constraints:

  • 1 <= n == nums.length <= 500
  • 1 <= nums[i] <= 105
  • 1 <= k <= n

Solution:

  1. 合理转化题意,拆解 power 的定义,当连续且递增时才会取最大值。因为递增,最大值则是这个 subarray 的最右侧值。
  2. 因为题目以 length 为 k 的 subarray 进行拆解,所以应联想到用 sliding window 来解决
  3. 将 power 取值转化为逻辑实现:
    • 连续递增 -> 前后差值为 1 -> 即 window block 内所有相邻 element 差值均为 1 时,条件成立
    • 定义 cnt 为以 i 结尾连续递增的 element 个数,我们默认第 i 个数计入统计。cnt default = 1
    • 第 i 个值,若跟 i-1 差值为 1 则 cnt++,(在 i-1 连续递增的数上+1,当前 i 也符合)若不为 1,则 cnt = 1 (从 i 重新开始,左边不连续递增,所以 i 为第一个符合的 element)
    • 在遍历时,便有公式 cnt = nums[i] - nums[i - 1] == 1 ? cnt + 1 : 1;
    • 考虑一开始第一个数没有左边,i - 1 越界了,则当 i==0 时默认为 1 – cnt = i == 0   nums[i] - nums[i - 1] != 1 ? 1 : cnt + 1; (当然也可以拆开写)
    • 因为左边可能都是递增的,所以 cnt>=k 代表向左 K 个肯定满足连续递增
class Solution {
    public int[] resultsArray(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Arrays.fill(ans, -1);
        int cnt = 0;
        for (int i = 0; i = k) {
                ans[i - k + 1] = nums[i];
            }
        }
        return ans;
    }
}

Contents