---
tags: leetcode, weekly contest,
---

# Contest 321

## Q1. No 2485, Find the Pivot Integer

### Description
Given a positive integer n, find the pivot integer x such that:

The sum of all elements between 1 and x inclusively equals the sum of all elements between x and n inclusively.
Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input.

- Example 1:

Input: n = 8
Output: 6
Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.

- Example 2:

Input: n = 1
Output: 1
Explanation: 1 is the pivot integer since: 1 = 1.

- Example 3:

Input: n = 4
Output: -1
Explanation: It can be proved that no such integer exist.

### Solution

1. **2 pointers**
- Time Complexity: $O(N)$
- Space Complexity: $O(1)$

 int pivotInteger(int n) {
        int left = 1, right = n;
        int l_sum = 0, r_sum  = 0;
        while(left < right) {
            if(l_sum < r_sum) {
                l_sum += left;
                left++;
            }
            else {
                r_sum += right;
                right--;
            }
        }
        return l_sum == r_sum ? left : -1;
}

2. **Math**

- Time Complexiy: $O(1)$
- Space Complexity: $O(1)$

int pivotInteger(int n) {
        int target = (n*n+n)/2;
        int pos_sol = sqrt(target);
        return pos_sol * pos_sol == target ? pos_sol : -1;
}

## Q2. 2486. Append Characters to String to Make Subsequence

### Description

You are given two strings s and t consisting of only lowercase English letters.

Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s.

**A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.**

### Solution

- Time Complexity: $O(min(M,N))$, M, N is the size of s, t

int appendCharacters(string s, string t) {
        int cur = 0;
        for(int i=0; i < s.length() && cur < t.length(); i++) {
            if(s[i] == t[cur]) {
                ++cur;
            }
        }
        return t.length() - cur;
}

## Q3. 2487, emove Nodes From Linked List

### Description
You are given the head of a linked list.

Remove every node which has a node with a strictly greater value anywhere to the right side of it.

Return the head of the modified linked list.

- Example 1:

Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.

- Example 2:

Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.

### Solution

- Time Complexity: $O(N)$
- Space Complexity: $O(N)$

ListNode* removeNodes(ListNode* head) {
        deque<ListNode*> node_store;
        // store satisfied nodes in stack
        while(head) {
            while(!node_store.empty() && node_store.top()->val < head->val) {
                // prevent mem leak
                // ListNode* removed = node_store.top();
                node_store.pop();
                // delete removed;
            }
            if(!node_store.empty())
                node_store.top()->next = head;
            node_store.push(head);
            head = head->next;
        }
        // build nodes to linked list
        /*
        while(!node_store.empty()) {
            ListNode* tail = head;
            head = node_store.top();
            head->next = tail;
            node_store.pop();
        }
        */
        return node_store.front();
}