Also, what do you think on this whole dilemma generally? Maybe, I should use something else instead of a builder? Or maybe, this problem is fundamentally unsolvable?

Your problem is solvable and the builder pattern is an appropriate pattern to use here.

Either you se the “standard”/”basic” builder pattern and add runtime validation to the build method

class MyClass {
  class Builder {
    private string mArgOne;
    private bool mArgOneSet = false;
    public Builder setArgOne(string aArgOne)
    {
      mArgOne = aArgOne;
      mArgOneSet = true;
      return this;
    }

    private string mArgTwo;
    private bool mArgTwoSet = false;
    public Builder setArgTwo(string aArgTwo)
    {
      mArgTwo = aArgTwo;
      mArgTwoSet = true;
      return this;
    }

    public MyClass build()
    {
      if (!mArgOneSet || !mArgTwoSet)
        throw exception;
      return new MyClass(mArgOne, mArgTwo);
    }
  }
  public Builder builder()
  {
    return new Builder();
  }
}

or you use an “elaborate” version of the builder pattern, where you use additional helper classes to ensure all mandatory arguments are provided (maybe in a defined order) before the build function can be found by the compiler:

class MyClass {
  class Builder0 {
    public Builder1 setArgOne(string aArgOne)
    {
      return new Builder1(mArgOne);
    }
  }

  class Builder1 { 
    private string mArgOne;
    private Builder1(string aArgOne)
    {
      mArgOne = aArgOne;
    }
    public Builder2 setArgTwo(string aArgTwo)
    {
      return new Builder2(mArgOne, mArgTwo);
    }
  }
  
  class Builder2 {
    private string mArgOne;
    private string mArgTwo;
    private Builder2(string aArgOne, string aArgTwo)
    {
      mArgOne = aArgOne;
      mArgTwo = aArgTwo;
    }
    public MyClass build()
    {
      return new MyClass(mArgOne, mArgTwo);
    }
  }
  public Builder0 builder()
  {
    return new Builder0();
  }
}

With another set of helper classes, you can make this also flexible in the order in which the mandatory arguments can be provided.

Suppose a class needs multiple properties of the same type. I don’t want a big constructor where the user can mess up the order of args (remember, they are of the same type, no compile-time errors)

My first advice is to rethink that design. Perhaps you can create custom classes for each argument that actually tell you at compile time what those objects are. For example, if you have email, create Email class. If you have user id, create UserId class and so on and so forth. This will definitiely increase safety of your code (order of args won’t be an issue anymore) and brings few more advantages (e.g. changing the underlying type of id is now trivial). You have strongly typed language, make use of that.

However this is not always possible. For example “Range” class that accepts two integers. Creating a separate class for each end sounds a bit artificial. And you will need to validate them (left end lower than right) ultimately.

Should the build() method throw (and also contain a lot of validation logic, proportional to the number of args)?

Of course build() should validate parameters before returning the object. Generally it is an antipattern to construct and pass around invalid objects. If some book says otherwise: throw it away. Although it is likely that it is not what Effective Java says (I didn’t read it though), nothing you wrote here suggests that.

Normally your builder would keep an “optional” field per each parameter. And during build() it checks whether required fields are set. If not returns/throws an error.

Personally I would return a “Result” object instead of throwing an exception. A “Result” object is an object that holds either the expected object or an error. I don’t know much about Java, but it must have or allow such constructions, no? But using exceptions is also acceptable, although a bit weird to my taste (it is not an exceptional situation when something doesn’t pass validation).

Those of you who read Bloch’s Effective Java may recall that he recommended the builder pattern in case there are multiple optional fields in the class. Using it for required args may be seen as misapplication of the pattern.

I kind of agree with that. But it is not a big deal, you can still use builder pattern. It brings other advantages. In fact validation itself is a good example. Even though it can be done in constructor, sometimes it is messy if for example validation depends on some configurable parameter, e.g. “max email length” (will you pass that to constructor as well?). Plus constructors cannot return “Result”, cannot be async (does Java support async/await?), and generally are limited. Another reason is that builders can reuse their own internal state, e.g. you can cache things, which is especially useful if those objects are immutable. And so on, and so on…

I think the real design issue are classes with a lot of mandatory constructor parameters. Normally, you start small, with a class having one or two mandatory constructor parameters. When you need to extend the class at a later point in time, try to care for backwards compatibility as good as you can. That means, the version with one or two parameters shall work as before, and additional parameters should be optional (with some good default value) in most cases.

Under these constraints, the mandatory parameters can be simply provided as mandatory constructor parameters for the initial Builder. Using your example from above, this leads to code like this:

MyClass.builder(requiredArg1, requiredArg2)   // it's unlikely this list will get much longer
    .setOptionalArgOne(argOne)
    .setOptionalArgTwo(argTwo)
    ...
    .build();

This gives us compile time safety, and is exactly what Bloch himself suggested in “Effective Java”, see this page where the relevant example from his book can be found. I also found this 10 year old Stackoverflow example, with a real-world case, which looks quite similar.

Of course, there are certain (rare) cases where this assumption will not hold, but I think one can go with the former approach as long as it works well, and refactor only when the number of mandatory parameters exceeds a certain number. One approach for refactoring such cases could be remodeling the required arguments by more specific types or wrapper types (like mentioned by freakish), or types which group them together. Another approach was shown in Bart’s answer – which will work, but seems to create a lot of boilerplate code for only a small benefit. I think, which of these alternative is “best” cannot be decided sensibly out of context, on the unspecific base of meaningless names like MyClass or argOne. Still, my first choice would be to start with the most simple solution, the one I scetched above.

Use convention over configuration and avoid cluttering the builder(s)'(s) implementation(s) with complex exception classes and validation logic. Apply the aphorism “a user interface is like a joke. if you have to explain it it’s not that good”. It might be that builded objects are poorly designed, over engineering the builders won’t fix the problem.