LeetCode Weekly Contest 485 Discussion and Solution

Problem-by-Problem Breakdown

Problem 1 - Vowel-Consonant Score

• If c > 0, the score = floor(v / c) where floor denotes rounding down to the nearest integer.
• Otherwise, the score = 0.

Approach

class Solution {
    public int vowelConsonantScore(String s) {
        int n = s.length();

        Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');

        int c = 0;
        int v = 0;

        for(int i = 0; i < n; i++){
            char ch = s.charAt(i);

            if(ch >= 'a' && ch <= 'z'){
                if(vowels.contains(ch)) v++;
                else c++;
            }
        }
        
        return c > 0 ? v / c : c;
    }
}

Problem 2 - Maximum Capacity Within Budget

Approach

Problem 3 - Design Auction System

• AuctionSystem(): Initializes the AuctionSystem object.
• void addBid(int userId, int itemId, int bidAmount): Adds a new bid for itemId by userId with bidAmount. If the same userId already has a bid on itemId, replace it with the new bidAmount.
• void updateBid(int userId, int itemId, int newAmount): Updates the existing bid of userId for itemId to newAmount. It is guaranteed that this bid exists.
• void removeBid(int userId, int itemId): Removes the bid of userId for itemId. It is guaranteed that this bid exists.
• int getHighestBidder(int itemId): Returns the userId of the highest bidder for itemId. If multiple users have the same highest bidAmount, return the user with the highest userId. If no bids exist for the item, return -1.

Approach

class AuctionSystem {

    Map<Integer, Map<Integer, Integer>> map;
    TreeMap<Integer, TreeMap<Integer, TreeSet<Integer>>> bid;

    public AuctionSystem() {
        map = new HashMap<>();
        bid = new TreeMap<>();
    }
    
    public void addBid(int userId, int itemId, int bidAmount) {
        if(!map.containsKey(itemId)) map.put(itemId, new HashMap<>());
        if(!bid.containsKey(itemId)) bid.put(itemId, new TreeMap<>());

        Map<Integer, Integer> itemMap = map.get(itemId);
        TreeMap<Integer, TreeSet<Integer>> bidMap = bid.get(itemId);
        
        int oldBid = itemMap.getOrDefault(userId, -1);
        
        itemMap.put(userId, bidAmount);

        if(bidMap.containsKey(oldBid)){
            TreeSet<Integer> bidSet = bidMap.get(oldBid);
            bidSet.remove(userId);

            if(bidSet.size() == 0) bidMap.remove(oldBid);
        }
        
        if(!bidMap.containsKey(bidAmount)){
            bidMap.put(bidAmount, new TreeSet<>());
        }

        bidMap.get(bidAmount).add(userId);
    }
    
    public void updateBid(int userId, int itemId, int bidAmount) {
        if(!map.containsKey(itemId)) map.put(itemId, new HashMap<>());
        if(!bid.containsKey(itemId)) bid.put(itemId, new TreeMap<>());

        Map<Integer, Integer> itemMap = map.get(itemId);
        TreeMap<Integer, TreeSet<Integer>> bidMap = bid.get(itemId);
        
        int oldBid = itemMap.getOrDefault(userId, -1);
        
        itemMap.put(userId, bidAmount);

        if(bidMap.containsKey(oldBid)){
            TreeSet<Integer> bidSet = bidMap.get(oldBid);
            bidSet.remove(userId);

            if(bidSet.size() == 0) bidMap.remove(oldBid);
        }
        
        if(!bidMap.containsKey(bidAmount)){
            bidMap.put(bidAmount, new TreeSet<>());
        }

        bidMap.get(bidAmount).add(userId);
    }
    
    public void removeBid(int userId, int itemId) {
        if(!map.containsKey(itemId)) map.put(itemId, new HashMap<>());
        if(!bid.containsKey(itemId)) bid.put(itemId, new TreeMap<>());

        Map<Integer, Integer> itemMap = map.get(itemId);
        TreeMap<Integer, TreeSet<Integer>> bidMap = bid.get(itemId);
        
        int oldBid = itemMap.getOrDefault(userId, -1);

        itemMap.remove(userId);
        
        if(bidMap.containsKey(oldBid)){
            TreeSet<Integer> bidSet = bidMap.get(oldBid);
            bidSet.remove(userId);

            if(bidSet.size() == 0) bidMap.remove(oldBid);
        }
    }
    
    public int getHighestBidder(int itemId) {
        Map<Integer, Integer> itemMap = map.getOrDefault(itemId, null);
        if(itemMap == null || itemMap.size() == 0) return -1;

        TreeMap<Integer, TreeSet<Integer>> bidMap = bid.getOrDefault(itemId, null);
        if(bidMap == null || bidMap.size() == 0) return -1;

        int maxBid = bidMap.lastKey();

        TreeSet<Integer> bidSet = bidMap.get(maxBid);

        if(bidSet.size() == 0) return -1;

        return bidSet.last();
    }
}

/**
 * Your AuctionSystem object will be instantiated and called as such:
 * AuctionSystem obj = new AuctionSystem();
 * obj.addBid(userId,itemId,bidAmount);
 * obj.updateBid(userId,itemId,newAmount);
 * obj.removeBid(userId,itemId);
 * int param_4 = obj.getHighestBidder(itemId);
 */

Problem 4 - Lexicographically Smallest String After Deleting Duplicate Characters

Approach

My Contest Experience