Week2.md

ToC

• September Week 2
  • 24.09.09 - 2326. Spiral Matrix IV
    • 나
    • gpt
  • 24.09.10 - 2807. Insert Greatest Common Divisors in Linked List
    • 나
    • gpt
  • 24.09.11 - 2220. Minimum Bit Flips to Convert Number
    • 나
    • gpt
  • 24.09.12 - 1684. Count the Number of Consistent Strings
    • 나
    • gpt
  • 24.09.13 - 1310. XOR Queries of a Subarray
    • 나
    • Solution
      • Iteratve Approach
      • Prefix XOR Array
  • 24.09.14 - 2419. Longest Subarray With Maximum Bitwise AND
    • 나
    • Solution
      • Approach: Longest consecutive sequence of the maximum value
  • 24.09.15 - 1371. Find the Longest Substring Containing Vowels in Even Counts
    • 나
    • Solution
      • Approach: Bitmasking

September Week 2

24.09.09 - 2326. Spiral Matrix IV

문제 링크

나

// 195ms, 147.44MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        // x: 0,1,0,-1 -> "1210"
        // y: 1,0,-1,0 -> "2101"
        
        std::string dx = "1210", dy ="2101";
        vector answer (m, vector(n, -1));
        vector visited (m, vector(n, 0));
        ListNode* now = head;

        int x{}, y{-1}, d{};
        int cnt{}, dCnt{};
        while(now && cnt < m * n) {
            int nx = x + dx[d] - '1', ny = y + dy[d] - '1';
            if(nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny]) { // 방향 전환
                d = (d+1)%4;
                ++dCnt;
                if(dCnt == 4) break; // 갈 곳이 없음.
                continue;
            }
            dCnt = 0;
            visited[nx][ny] = 1;
            answer[nx][ny] = now->val;
            now = now ->next;
            x = nx, y = ny;
            ++cnt;
        }

        return answer;
    }
};

gpt

The Spiral Matrix IV problem on LeetCode involves filling a matrix of size m x n with values from a linked list in spiral order, starting from the top-left corner. If there are remaining cells after exhausting the linked list, they should be filled with -1.

Approach:

1. Initialize the Matrix: Create a matrix ans of size m x n and initialize all its elements to -1.
2. Set Directional Boundaries: Use an array to represent four possible movement directions: right, down, left, and up.
3. Iterate through the Linked List:
   • Begin at the top-left corner.
   • Move in a spiral pattern, and at each step, check if the next move is valid (i.e., within the matrix bounds and not already filled).
   • If an invalid move is detected, change direction and continue filling.
4. Fill the Matrix: For each node in the linked list, assign its value to the current cell and move to the next cell. Once the linked list is exhausted, leave the remaining cells as -1.

Code in C++:

// 162ms, 130.48MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> ans(m, vector<int>(n, -1));
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0, d = 0;
        
        for (ListNode* curr = head; curr; curr = curr->next) {
            ans[x][y] = curr->val;
            int nx = x + dirs[d][0], ny = y + dirs[d][1];
            
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || ans[nx][ny] != -1) {
                d = (d + 1) % 4;
                nx = x + dirs[d][0];
                ny = y + dirs[d][1];
            }
            x = nx;
            y = ny;
        }
        
        return ans;
    }
};

Time Complexity:

• $O(m * n)$ since we traverse each cell of the matrix once, and each step involves checking bounds and filling a value.

Space Complexity:

• $O(m * n)$ for storing the matrix.

This approach efficiently simulates the spiral filling, and handles edge cases like small matrix sizes and lists shorter than m * n.

24.09.10 - 2807. Insert Greatest Common Divisors in Linked List

문제 링크

나

// 41ms, 35.6MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* now = head;
        while(now) {
            ListNode* next = now->next;
            if(next == nullptr) break;
            int num = [](int a ,int b) -> int {
                while(b) {
                    int tmp = b;
                    b = a%b;
                    a = tmp;
                }
                return a;
            } (now->val, next->val);
            ListNode *tmp = new ListNode{num, next};
            now->next = tmp;

            now = next;
        }
        return head;
    }
};

// 38ms, 35.5MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* now = head;
        while(now) {
            ListNode* next = now->next;
            if(next == nullptr) break;
            int num = gcd(now->val, next->val);
            ListNode *tmp = new ListNode{num, next};
            now->next = tmp;

            now = next;
        }
        return head;
    }
private:
    int gcd(int a,int b) {
        if(b==0) return a;
        return gcd(b, a%b);
    }
};

gpt

To solve the problem "Insert Greatest Common Divisors in Linked List," you need to modify the linked list by inserting a new node between every two adjacent nodes. The value of the new node should be the Greatest Common Divisor (GCD) of the values of these two adjacent nodes. Here's a step-by-step approach to solve this:

Steps:

1. Traverse the Linked List: Start at the head of the linked list and traverse through each node.
2. Calculate GCD: For every pair of adjacent nodes, compute the GCD of their values.
3. Insert a New Node: Create a new node with the GCD value and insert it between the two adjacent nodes.
4. Continue: Move to the next node and repeat the process until the end of the list.

Algorithm in C++:

// 37ms, 35.58MB
class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* curr = head;
        while (curr->next != nullptr) {
            // Calculate GCD of curr and next node values
            int gcdValue = gcd(curr->val, curr->next->val);
            // Create a new node with the GCD value
            ListNode* newNode = new ListNode(gcdValue, curr->next);
            // Insert the new node between curr and the next node
            curr->next = newNode;
            // Move curr to the node after the newly inserted one
            curr = newNode->next;
        }
        return head;
    }

private:
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
};

Explanation:

• GCD Calculation: The gcd() function uses the Euclidean algorithm to compute the GCD of two integers.
• Insertion Logic: The loop goes through each node in the list and calculates the GCD between the current node's value and the next node's value. A new node with the GCD is created and inserted between these two nodes. The traversal continues with the next node after the newly inserted one.

Time Complexity:

The time complexity is $O(n \log M)$, where $n$ is the number of nodes in the linked list, and $M$ is the maximum value of the node values. This accounts for both the list traversal and the GCD calculation.

24.09.11 - 2220. Minimum Bit Flips to Convert Number

문제 링크

나

// 0ms, 7.5MB
class Solution {
public:
    int minBitFlips(int start, int goal) {
        int tmp = start ^ goal;
        int cnt{};
        while(tmp) {
            if(tmp&1) ++cnt;
            tmp >>= 1;
        }
        return cnt;
    }
};

gpt

The problem "Minimum Bit Flips to Convert Number" can be solved using a simple bit manipulation technique. Here's how:

Problem Summary:

Given two integers start and goal, the task is to determine the minimum number of bit flips required to convert start into goal. A "bit flip" refers to changing a bit from 0 to 1 or from 1 to 0 in the binary representation.

Approach:

1. Use XOR: Perform XOR (^) between start and goal. XOR will set bits to 1 where the bits of start and goal differ and to 0 where they are the same.
2. Count 1s in the Result: After XOR, count the number of 1s in the result. Each 1 represents a bit that needs to be flipped.

Example:

For start = 10 and goal = 7:

• Binary of 10 is 1010.
• Binary of 7 is 0111.
• XOR of 1010 ^ 0111 = 1101. There are 3 ones, so 3 bit flips are needed.

C++ Code Implementation:

// 3ms, 7.7MB
class Solution {
public:
    int minBitFlips(int start, int goal) {
        int xorResult = start ^ goal;
        int bitCount = 0;
        while (xorResult > 0) {
            bitCount += xorResult & 1;
            xorResult >>= 1;
        }
        return bitCount;
    }
};

Time Complexity:

• $O(log(max(start, goal)))$: This is because we are counting the number of bits in the XOR result.
• Space Complexity: $O(1)$, since we use a constant amount of space.

24.09.12 - 1684. Count the Number of Consistent Strings

문제 링크

나

// 46ms, 33.92MB
class Solution {
public:
    int countConsistentStrings(string allowed, vector<string>& words) {
        int dat[27]{};
        for(char c : allowed) {
            dat[c - 'a'] = 1;
        }

        int answer{};
        for(string word : words) {
            auto ret = [&]() -> bool {
                for(char c : word) {
                    if(!dat[c - 'a']) return false;
                }
                return true;
            } ();
            if(ret) ++answer;
        }

        return answer;
    }
};

gpt

The problem "Count the Number of Consistent Strings" on LeetCode asks you to find how many strings in an array consist only of characters found in a given string called allowed.

Solution Approach:

1. Input: A string allowed and an array of strings words.
2. Output: Count how many strings in words consist only of characters from allowed.
3. Plan:
   • Convert the allowed string into a set for fast lookups.
   • For each word, check if all its characters belong to this set.
   • Count the words that meet the condition.

C++ Code:

// 43ms, 34.11MB
class Solution {
public:
    int countConsistentStrings(string allowed, vector<string>& words) {
        unordered_set<char> allowed_set(allowed.begin(), allowed.end());
        int count = 0;
        for (const auto& word : words) {
            bool is_consistent = true;
            for (char c : word) {
                if (allowed_set.find(c) == allowed_set.end()) {
                    is_consistent = false;
                    break;
                }
            }
            if (is_consistent) {
                ++count;
            }
        }
        return count;
    }
};

Explanation:

1. Set for allowed characters: This speeds up the check for each character in words.
2. Loop over words: For each word, verify if all characters are in the allowed set.
3. Return the count of consistent strings.

24.09.13 - 1310. XOR Queries of a Subarray

문제 링크

나

// 52ms, 42.22MB
class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        const int SIZE = static_cast<int>(arr.size());
        vector<int> preXor(SIZE + 1, 0);
        for(int s{}, e{SIZE};s<e;++s){
            preXor[s+1] = preXor[s] ^ arr[s];
        }

        vector<int> answer;
        for(vector<int>& query : queries) {
            int start = query[0], finish = query[1]; // [0, 1]
            answer.push_back(preXor[finish + 1] ^ preXor[start]);
        }

        return answer;
    }
};

Solution

Iteratve Approach

// 1960ms, 41.83MB
// Iterative Approach
class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int> result;
        // Process each query
        for (const auto& q : queries) {
            int xorSum = 0;
            // Calculate XOR for the range [q[0], q[1]]
            for (int i = q[0]; i <= q[1]; i++) {
                xorSum ^= arr[i];
            }
            result.push_back(xorSum);
        }
        return result;
    }
};

Prefix XOR Array

// 69ms, 42.13MB
// Prefix XOR Array
class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int n = arr.size();
        vector<int> prefixXOR(n + 1, 0);

        // Build prefix XOR array
        for (int i = 0; i < n; i++) {
            prefixXOR[i + 1] = prefixXOR[i] ^ arr[i];
        }

        vector<int> result;
        // Process each query using prefix XOR
        for (const auto& q : queries) {
            result.push_back(prefixXOR[q[1] + 1] ^ prefixXOR[q[0]]);
        }
        return result;
    }
};

24.09.14 - 2419. Longest Subarray With Maximum Bitwise AND

문제 링크

나

// 108ms, 84.96MB
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int answer{}, maxVal{};
        for(int num : nums) {
            maxVal = max(maxVal, num);
        }

        int cnt{};
        for(int num : nums) {
            if(maxVal == num) ++cnt;
            else cnt = 0;

            answer = max(answer, cnt);
        }

        return answer;
    }
};

한 번에 답 구하고 싶었는데, 조금 꼬였다.

Solution

링크

Overview

We need to find the longest subarray in an integer array where the bitwise AND of all elements equals the maximum possible bitwise AND of any subarray. The bitwise AND results in a value that is always less than or equal to the operands. This operation is commonly used in fields like network filtering, hardware design, and cryptography for tasks such as subnet masking, configuration checks, and data analysis.

Approach: Longest consecutive sequence of the maximum value

Intuition

To understand this problem, we first need to understand what a bitwise AND operation is. In simple terms, a bitwise AND operation takes two binary representations of an integer and performs the logical AND operation on each pair of the corresponding bits. If both bits are 1, the result is 1; otherwise, it's 0.

For example, take the numbers 12 (which is 1100 in binary) and 7 (0111 in binary).

Performing a bitwise AND on these numbers gives the following:

Bit Position	3rd Bit	2nd Bit	1st Bit	0th Bit
Number 12	1	1	0	0
Number 7	0	1	1	1
Bitwise AND	0	1	0	0

As we can see, the result is 0100, which is the binary representation of 4.

Now, let’s look at the problem. We're given an array, and the goal is to find a subarray where the bitwise AND of all the numbers is as large as possible. A subarray is a continuous portion of the array, and we want to return the length of the subarray that has the highest bitwise AND value.

The maximum possible bitwise AND of a subarray would be the maximum number in the array itself. This is because the bitwise AND operation with a larger number and a smaller number would always result in a number less than or equal to the smaller number. Therefore, the maximum possible bitwise AND of a subarray can only be achieved when all the numbers in the subarray are equal to the maximum number in the array.

Let’s look at some examples of subarrays and their bitwise AND results:

Subarray	Bitwise AND Calculation	Result
[4, 6]	4 AND 6 = 0100 AND 0110	0100 = 4
[4, 6, 7]	4 AND 6 AND 7 = 0100 AND 0110 AND 0111	0100 = 4
[4, 6, 7, 8]	4 AND 6 AND 7 AND 8 = 0100 AND 0110 AND 0111 AND 1000	0000 = 0
[6, 7]	6 AND 7 = 0110 AND 0111	0110 = 6
[6, 7, 8]	6 AND 7 AND 8 = 0110 AND 0111 AND 1000	0000 = 0
[7, 8]	7 AND 8 = 0111 AND 1000	0000 = 0
[8, 8]	8 AND 8 = 1000 AND 1000	1000 = 8

From this, we can see that the largest bitwise AND can only be achieved when all the elements in the subarray are equal to the maximum number. So, the task is to find the longest subarray where all the numbers are the maximum value in the array.

Algorithm

1. Initialize max_val = 0, ans = 0, and current_streak = 0 to track the maximum value, the length of the longest subarray, and the current streak of elements, respectively.
2. Iterate through each element num in the array nums.
3. If max_val < num, update max_val to num, and reset ans and current_streak to 0 since a new maximum value is found.
4. If max_val == num, increment current_streak by 1 because the current element is equal to the maximum value.
5. If max_val != num, reset current_streak to 0 as the current element breaks the streak of numbers equal to the maximum value.
6. Update ans to be the maximum of ans and current_streak to ensure ans holds the length of the longest subarray with the maximum value.
7. After the loop finishes, return ans, which represents the length of the longest subarray where the bitwise AND equals the maximum value.

Implementation

// 89ms, 84.88MB
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int maxVal = 0, ans = 0, currentStreak = 0;

        for (int num : nums) {
            if (maxVal < num) {
                maxVal = num;
                ans = currentStreak = 0;
            }

            if (maxVal == num) {
                currentStreak++;
            } else {
                currentStreak = 0;
            }

            ans = max(ans, currentStreak);
        }
        return ans;
    }
};

Let $N$ be the length of nums.

• Time Complexity: $O(N)$
  The time complexity is $O(N)$ because the function processes each element of the nums list exactly once. This is done through a single loop that iterates over the array. Each operation inside the loop—whether it's comparisons, assignments, or finding the maximum—takes constant time. As a result, the total time required scales linearly with the size of the input array.

• Space Complexity: $O(1)$
  The function uses a fixed amount of extra space regardless of the size of the input array nums. Specifically, it only requires a few variables (max_val, ans, current_streak, and num) to keep track of intermediate values. This fixed space usage means the space complexity remains constant.

24.09.15 - 1371. Find the Longest Substring Containing Vowels in Even Counts

문제 링크

나

Solution Code 참고.

Solution

Approach: Bitmasking

Intuition

Given a string s, we need to find the length of the longest substring in which any vowel present must appear an even number of times. A brute force approach would involve iterating through every substring and counting vowels, but this would result in a Time Limit Exceeded (TLE). Instead, we need to think of a more efficient solution, aiming for a linear or log-linear time complexity.

Observe that we don't need to know the exact count of the vowels to solve this problem; we only need to know the parity of each vowel (whether it appears an even or odd number of times). The parity of each vowel can be stored in a boolean or bit, where 0 means even and 1 means odd. We need five bits to track the parity of all five vowels (a, e, i, o, u), resulting in $2^5 = 32$ possible states.

We can assign the first bit to a, the second to e, and so on. The state of the vowels can be represented as a binary string. For instance, 00000 means all vowels have even counts, while 10000 means only a has an odd count. By converting these binary states to integers, we can assign values to the vowels: a = 1, e = 2, i = 4, o = 8, and u = 16. If both a and i have odd counts, their total value would be 1 + 4 = 5. A total value of 0 means all vowels have even counts.

To find substrings with even vowels, we can use the XOR operator to update and track the parity of the vowels. If a vowel appears an even number of times, the result of XOR will be 0; if it appears an odd number of times, the result will be 1.

We compute a running XOR for each vowel as we traverse the string. To check for substrings with even vowels, we consider two cases:

1. If the current XOR value is 00000 (i.e., all vowels have even counts), the substring from the start of the string to the current position contains even vowels.
2. If the current XOR value has occurred before, the substring between the first occurrence of that XOR value and the current position also contains even vowels.

Algorithm

1. Initialize an integer variable prefixXOR and set it to 0.
2. Initialize a character array characterMap[26] where specific vowel characters ('a', 'e', 'i', 'o', 'u') have unique mask values (1, 2, 4, 8, 16).
3. Initialize an array mp of size 32, where all elements are set to -1. This will store the index of the first occurrence of each prefixXOR value.
4. Initialize an integer variable longestSubstring and set it to 0.
5. Iterate through each character in the string s:
   • Update prefixXOR by XORing it with the mask value of the current character (from characterMap).
   • If the current prefixXOR value is not found in mp and prefixXOR is not 0:
     • Store the current index in mp at the position corresponding to prefixXOR.
   • Update longestSubstring by comparing it with the difference between the current index and mp[prefixXOR].
6. Return longestSubstring as the final result.

Implementation

// 42ms, 17.66MB
class Solution {
public:
    int findTheLongestSubstring(string s) {
        int prefixXOR = 0;
        // Store the masks of all letters in an array.
        int characterMap[26] = {0};
        characterMap['a' - 'a'] = 1;
        characterMap['e' - 'a'] = 2;
        characterMap['i' - 'a'] = 4;
        characterMap['o' - 'a'] = 8;
        characterMap['u' - 'a'] = 16;
        // Initialize mp to store the previous index with this prefixXOR value.
        vector<int> mp(32, -1);
        int longestSubstring = 0;

        for (int i = 0; i < s.length(); i++) {
            // If the current character is a vowel, find it's prefix XOR and add
            // it in the map.
            prefixXOR ^= characterMap[s[i] - 'a'];
            if (mp[prefixXOR] == -1 and prefixXOR != 0) mp[prefixXOR] = i;

            // If the value of prefixXOR exists in the map, find the longest
            // subarray.
            longestSubstring = max(longestSubstring, i - mp[prefixXOR]);
        }

        return longestSubstring;
    }
};

Complexity Analysis

Let $m$ be the size of the given s string.

• Time complexity: $O(n)$
  We iterate through the string s exactly once. Apart from this, all operations are constant time. Therefore, the total time complexity is given by $O(\text{max}(m, n))$.

• Space complexity: $O(1)$
  Apart from the characterMap and mp array, no additional space is used to solve the problem. Therefore, the space complexity is given by $O(26) + O(32) ≈ O(1)$.