01. Arrays & Strings

Arrays Strings

Arrays vs. Strings:

• Array and string questions are often interchangeable because strings are arrays of characters.
• Analyze the problem: Could the solution for an array problem apply to strings, and vice versa?

---

Hash Tables and Collision Resolution

• Building a Hash Table:

  • Use an array of linked lists to handle collisions via chaining.
  • Hash function maps keys to indices; collisions occur when keys map to the same index.

• C++ STL Implementation:

  • std::unordered_map abstracts hash tables.
  • Uses open addressing or chaining for collision resolution.

---

Arrays vs. Vectors in C++

• Key Differences:

  • Arrays: Fixed size, contiguous memory, no dynamic resizing.
  • Vectors (std::vector): Resizable, manages memory automatically.

• Resizable Array Mechanics:

  • Doubles its capacity when resizing is needed.
  • Amortized time complexity for push_back: O(1) (due to infrequent resizing).

---

String Builders (String Stream in C++)

• Why Use String Builders?

  • Concatenating strings repeatedly creates new copies, increasing memory and time costs.
  • String builders avoid these overheads by appending directly to a buffer.

• Example: joinWords Problem:

  • Direct concatenation (e.g., word1 + word2 + word3) creates multiple temporary strings.
  • Using std::ostringstream (string stream) builds the final string more efficiently.

---

Practice Exercises

1. Implement your own StringBuilder using a dynamic buffer.
2. Create a custom Hash Table using an array of linked lists for collision resolution.
3. Build an ArrayList with dynamic resizing.

---

Tips for Solving Array/List Questions

1. Understand the problem constraints (e.g., fixed size vs. dynamic size).
2. Use helper data structures like hash tables or fixed-size arrays for optimizations.
3. Break the problem into logical steps (e.g., iterate, transform, aggregate).

---

Two Pointer / Sliding Window Techniques

• Common Use Cases:

  • Pair-Finding: Identify pairs in a sorted array with a target sum.
  • Merging Sorted Arrays: Traverse both arrays with two pointers.
  • Subarray Searches: Find subarrays with specific properties (e.g., max sum, target sum).

• Why Use These Techniques?

  • Efficient for linear time complexity (O(n)) solutions.

---

Benefits of std::reverse

• Reverses elements in-place.
• Time Complexity: O(n).

---

Counting Characters with Fixed-Size Arrays

• Use an array of size 128 (for ASCII) to count character frequencies.
• Efficient for problems like permutation checks or character frequency analysis.

---

Bit Manipulation in String/Array Questions

• Example Use Cases:
  • Check unique characters in a string using bit masks.
  • Represent subsets of arrays with bit masks for efficient comparison.

---

std::string::find for Searches

• Common Usage:

  • Check substring existence.
  • Verify rotations by concatenating a string with itself and using find.

• Time Complexity: O(n) for substring searches in typical cases.

---

General Takeaways

• Focus on problem-specific optimizations (e.g., hash tables for lookups, string builders for concatenations).
• Understand the trade-offs between arrays and dynamic data structures.
• Leverage C++ STL functions for simplicity but know their underlying complexities.