DSA: Arrays
For interviews
Submitted: 0%
Reviewed: 0%
The array tracker covers the fundamentals of arrays, a data structure used to store and access multiple elements under a single name. Topics include array creation, accessing elements, modifying array values, array traversal, and common array algorithms. Students will learn to efficiently manipulate and work with arrays to solve programming problems effectively.
- Day 1
Concept:
Assignments:
[{"_type":"codeBlock","language":"plaintext","code":"Example 1:\n\nInput: s = \"hello\"\nOutput: \"holle\""},{"_type":"codeBlock","language":"plaintext","code":"Constraints:\n\n1 <= s.length <= 3 * 10^5\ns consists of printable ASCII characters."}]
- Day 2
Concept:
Assignments:
[{"_type":"callout","variant":"info","text":"Important Details: The product must fit in a 32-bit integer. You cannot use division to solve this. The algorithm should run in O(n) time."},{"_type":"heading","level":2,"text":"Example 1"},{"_type":"heading","level":3,"text":"Input:"},{"_type":"paragraph","spans":[{"text":"\n nums = [1, 2, 3, 4]\n "}]},{"_type":"heading","level":3,"text":"Output:"},{"_type":"paragraph","spans":[{"text":"\n [24, 12, 8, 6]\n "}]},{"_type":"heading","level":3,"text":"Explanation:"},{"_type":"paragraph","spans":[{"text":"For index 0: 2×3×4 = 24"}]},{"_type":"paragraph","spans":[{"text":"For index 1: 1×3×4 = 12"}]},{"_type":"paragraph","spans":[{"text":"For index 2: 1×2×4 = 8"}]},{"_type":"paragraph","spans":[{"text":"For index 3: 1×2×3 = 6"}]},{"_type":"heading","level":2,"text":"Example 2"},{"_type":"heading","level":3,"text":"Input:"},{"_type":"paragraph","spans":[{"text":"\n nums = [-1, 1, 0, -3, 3]\n "}]},{"_type":"heading","level":3,"text":"Output:"},{"_type":"paragraph","spans":[{"text":"\n [0, 0, 9, 0, 0]\n "}]},{"_type":"heading","level":3,"text":"Explanation:"},{"_type":"paragraph","spans":[{"text":"\n At index 2, there's a zero, so every other product becomes 0.\n "}]},{"_type":"callout","variant":"info","text":"2 ≤ nums.length ≤ 10⁵ -30 ≤ nums[i] ≤ 30 The product for each index is guaranteed to fit in a 32-bit signed integer."}]
- Day 3
Concept:
Assignments:
[{"_type":"paragraph","spans":[{"text":"Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter."}]}]
- Day 4
Concept:
Assignments:
[{"_type":"paragraph","spans":[{"text":"\nYou are given an m x n integer grid accounts where accounts[i][j] is the amount of money the ith customer has in the jth bank. Return the wealth that the richest customer has.\n\n\n\nA customer's wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.\n\n\n\n \nConstraints:\n\n\n\nm == accounts.length\n\nn == accounts[i].length\n\n1 <= m, n <= 50\n\n1 <= accounts[i][j] <= 100\n\n\n\n\nExample 1:\n\nInput: accounts = [[1,2,3],[3,2,1]]\n\nOutput: 6\n\nExplanation:\n\n1st customer has wealth = 1 + 2 + 3 = 6\n\n2nd customer has wealth = 3 + 2 + 1 = 6\n\nBoth customers are considered the richest with a wealth of 6 each, so return 6.\n\n\n\nExample 2:\n\nInput: accounts = [[1,5],[7,3],[3,5]]\n\nOutput: 10\n\nExplanation: \n\n1st customer has wealth = 6\n\n2nd customer has wealth = 10 \n\n3rd customer has wealth = 8\n\nThe 2nd customer is the richest with a wealth of 10.\n\n\n\n\n\n"}]}]
- Day 5
Concept:
Assignments:
[{"_type":"paragraph","spans":[{"text":"\nYou have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.\n\n\nGiven an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.\n\n\n\nConstraints:\n\n\n1 <= flowerbed.length <= 2 * 10^4\n\nflowerbed[i] is 0 or 1.\n\nThere are no two adjacent flowers in flowerbed.\n\n0 <= n <= flowerbed.length\n\n\n\n\nExample 1:\n\nInput: flowerbed = [1,0,0,0,1], n = 1\n\nOutput: true\n\n\n\n\nExample 2:\n\nInput: flowerbed = [1,0,0,0,1], n = 2\n\nOutput: false\n\n\n"}]}]
- Day 6
Concept:
Resources:
Assignments:
[{"_type":"paragraph","spans":[{"text":"You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr: 1. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list. 2. Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers. 3. Keep repeating the steps again, alternating left to right and right to left, until a single number remains. Given the integer n, return the last number that remains in arr. Example: Input: n = 9 Output: 6 Explanation: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] arr = [2, 4, 6, 8] arr = [2, 6] arr = [6]"}]}]
- Day 7
Concept:
Resources:
Assignments:
[{"_type":"paragraph","spans":[{"text":"\nGiven an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher's h-index.\n\n\n\nThe h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.\n\n\n\n\nExample 1:\n\nInput: citations = [3,0,6,1,5]\n\nOutput: 3\n\nExplanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.\n\nSince the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.\n\n\n\n"}]}]
- Day 8
Concept:
Resources:
Assignments:
[{"_type":"paragraph","spans":[{"text":"\n\nYou want to water n plants in your garden with a watering can. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the ith plant is located at x = i. There is a river at x = -1 that you can refill your watering can at.\n\n\n\nEach plant needs a specific amount of water. You will water the plants in the following way:\n\n\n\nWater the plants in order from left to right.\n\n\nAfter watering the current plant, if you do not have enough water to completely water the next plant, return to the river to fully refill the watering can.\n\n\nYou cannot refill the watering can early.\n\n\n\nYou are initially at the river (i.e., x = -1). It takes one step to move one unit on the x-axis.\n\n\n\nGiven a 0-indexed integer array plants of n integers, where plants[i] is the amount of water the ith plant needs, and an integer capacity representing the watering can capacity, return the number of steps needed to water all the plants.\n\n\n\n\nConstraints:\n\n\n\nn == plants.length\n\n1 <= n <= 1000\n\n1 <= plants[i] <= 10^6\n\nmax(plants[i]) <= capacity <= 10^9\n\n\n\n\nExample 1:\n\n\n\nInput: plants = [2,2,3,3], capacity = 5\n\nOutput: 14\n\n\nExplanation: Start at the river with a full watering can:\n\n- Walk to plant 0 (1 step) and water it. Watering can has 3 units of water.\n\n- Walk to plant 1 (1 step) and water it. Watering can has 1 unit of water.\n\n- Since you cannot completely water plant 2, walk back to the river to refill (2 steps).\n\n- Walk to plant 2 (3 steps) and water it. Watering can has 2 units of water.\n\n- Since you cannot completely water plant 3, walk back to the river to refill (3 steps).\n\n- Walk to plant 3 (4 steps) and water it.\n\nSteps needed = 1 + 1 + 2 + 3 + 3 + 4 = 14.\n\n\n\nExample 2:\n\n\n\nInput: plants = [1,1,1,4,2,3], capacity = 4\n\nOutput: 30\n\n\nExplanation: Start at the river with a full watering can:\n\n- Water plants 0, 1, and 2 (3 steps). Return to river (3 steps).\n\n- Water plant 3 (4 steps). Return to river (4 steps).\n\n- Water plant 4 (5 steps). Return to river (5 steps).\n\n- Water plant 5 (6 steps).\n\nSteps needed = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30.\n\n\n\nExample 3:\n\n\n\nInput: plants = [7,7,7,7,7,7,7], capacity = 8\n\nOutput: 49\n\n\nExplanation: You have to refill before watering each plant.\n\nSteps needed = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49.\n\n\n"}]}]
- Day 9
Concept:
Resources:
Assignments:
[{"_type":"paragraph","spans":[{"text":"\nYou are given an array prices where prices[i] is the price of a given stock on the ith day.\n\n\nYou want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.\n\n\nReturn the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.\n\n\n\n\nConstraints:\n\n\n\n1 <= prices.length <= 10^5\n\n0 <= prices[i] <= 10^4\n\n\n\n\nExample 1:\n\n\nInput: prices = [7,1,5,3,6,4]\n\nOutput: 5\n\nExplanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.\nNote that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.\n\n\n\nExample 2:\n\n\nInput: prices = [7,6,4,3,1]\n\nOutput: 0\n\nExplanation: In this case, no transactions are done and the max profit = 0.\n\n \n\n\n\n"}]}]
- Day 10
Concept:
Resources:
Assignments:
[{"_type":"paragraph","spans":[{"text":"\n\nGiven an array nums of size n, return the majority element.\n\n\nThe majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.\n\n\n\n \nConstraints:\n\n\nn == nums.length\n\n1 <= n <= 5 * 10^4\n\n-10^9 <= nums[i] <= 10^9\n\n\n \nExample 1:\n\n\nInput: nums = [3,2,3]\n\nOutput: 3\n\n\nExample 2:\n\n\nInput: nums = [2,2,1,1,1,2,2]\n\nOutput: 2\n\n \n\n"}]}]
