DSA - Arrays and Strings
Studied by 0 people
Learn
Practice Test
Spaced Repetition
Match
Flashcards1/68
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
69 Terms
What is an array?
A data structure storing a collection of elements of the same type in contiguous memory, accessible by index.
What is a string?
A sequence of characters, often conceptually an array of characters. Immutable in languages like Python and Java.
Array: Time complexity for accessing an element by index?
O(1)
Array: Time complexity for inserting/deleting in the middle?
O(N)
String: Time complexity for concatenation (creating new string)?
O(N+M) where N and M are string lengths.
What is the Two Pointers technique?
Uses two integer indices to traverse an array/string, often from different ends or at different speeds, to process pairs or find conditions.
When should you use Two Pointers?
Reversing arrays/strings, finding pairs in sorted arrays, palindrome detection, partitioning.
What is the Sliding Window technique?
Maintains a subsegment (window) that slides over data to find a part satisfying certain properties (e.g., max sum subarray, longest substring with k distinct chars).
When should you use Sliding Window?
Problems asking for max/min sum/average of a fixed/variable size subarray/substring, or longest/shortest substring with certain properties.
What is a Hash Map (or Hash Set)?
Data structure for O(1) average time key-value (map) or key (set) storage, lookup, and deletion. Useful for counting, existence checks.
When should you use a Hash Map/Set?
Counting frequencies, checking for duplicates, Two Sum type problems, anagrams.
What is the Prefix Sum technique?
Precalculating sums (or products, XORs, etc.) up to each index P[i] = arr[0] + … + arr[i], allowing O(1) range sum queries (P[k] - P[j-1]).
When should you use Prefix Sum?
Frequent range sum queries, finding equilibrium/pivot indices, problems involving sums/products to left/right of an element.
What is often a crucial preprocessing step for array problems, enabling techniques like two-pointers or binary search?
Sorting the array.
Two Sum (LeetCode): Problem Summary
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
Two Sum: Optimal technique?
Hash Map.
Two Sum: How to recognize Hash Map applies?
Need to find two numbers summing to a target; hash map allows O(1) lookup for the complement.
Two Sum: Time/Space Complexity (Hash Map)?
Time: O(N), Space: O(N).
Best Time to Buy and Sell Stock: Problem Summary
Given stock prices over days, find max profit from one buy and one later sell.
Best Time to Buy and Sell Stock: Key technique?
One Pass (Kadane's variant): track min price so far and calculate max profit.
Best Time to Buy and Sell Stock: Time/Space Complexity?
Time: O(N), Space: O(1).
Contains Duplicate: Problem Summary
Return true if any value appears at least twice in an array, false otherwise.
Contains Duplicate: Key technique(s)?
Hash Set or Sorting.
Contains Duplicate: How to recognize Hash Set applies?
Need to efficiently check for existence of elements seen before.
Contains Duplicate: Time/Space (Hash Set)?
Time: O(N), Space: O(N).
Contains Duplicate: Time/Space (Sorting)?
Time: O(NlogN), Space: O(1) or O(N) depending on sort.
Valid Anagram: Problem Summary
Given two strings s and t, return true if t is an anagram of s.
Valid Anagram: Key technique(s)?
Hash Map (character counts) or Sorting.
Valid Anagram: How to recognize Hash Map applies?
Problem involves comparing character frequencies.
Valid Anagram: Time/Space (Hash Map)?
Time: O(N), Space: O(K) (K=alphabet size, so effectively O(1)).
Valid Anagram: Time/Space (Sorting)?
Time: O(NlogN), Space: O(N).
Longest Substring Without Repeating Characters: Problem Summary
Find the length of the longest substring in s without repeating characters.
Longest Substring Without Repeating Characters: Key technique?
Sliding Window with Hash Set/Map.
Longest Substring Without Repeating Characters: How to recognize Sliding Window applies?
Looking for "longest substring" with a property ("without repeating characters"). Hash set/map tracks chars in window.
Longest Substring Without Repeating Characters: Time/Space?
Time: O(N), Space: O(K) (K=alphabet size or min(N, alphabet size)).
Minimum Size Subarray Sum: Problem Summary
Given nums and target, find minimal length of a contiguous subarray whose sum is >= target.
Minimum Size Subarray Sum: Key technique?
Sliding Window (variable size).
Minimum Size Subarray Sum: How to recognize Sliding Window applies?
"Minimal length" of "contiguous subarray" with a sum condition.
Minimum Size Subarray Sum: Time/Space?
Time: O(N), Space: O(1).
Reverse String: Problem Summary
Reverse an array of characters in-place.
Reverse String: Key technique?
Two Pointers.
Reverse String: How to recognize Two Pointers apply?
Explicit request for in-place reversal of a sequence.
Reverse String: Time/Space?
Time: O(N), Space: O(1).
In Python, how can you efficiently build a string from a list of characters or smaller strings?
Use "".join(listofstrings).
Why is s += char in a loop inefficient for building strings in Python/Java?
Strings are immutable, so each += creates a new string object, leading to O(N^2) complexity for N appends.
General pattern for Sliding Window (variable size): Expand window by adding element at right.
While condition met/violated: update result, shrink window by removing element at left, move left. Move right.
General pattern for Two Pointers (opposite ends): left = 0, right = len-1.
While left < right: process arr[left], arr[right]; move left and/or right based on logic.
What does 'contiguous memory locations' mean for an array?
Elements are stored one after another in memory, without gaps, allowing for pointer arithmetic and efficient indexed access.
What does 'immutable string' mean?
Once a string object is created, its content (sequence of characters) cannot be changed. Operations that seem to modify it actually create a new string object.